POJ 3694 Network
3004 ワード
テーマ:
1つの連通図Gに、ある辺を加えた後の図にどれだけの割れ目があるかを聞く.
問題解決の考え方:
1.Tarjanアルゴリズムを用いてすべてのエッジと各点の親ノードを求め、記録する.各ノードを記録する親ノードは、深いツリーを形成することができます.
2.LCA(最近の公的祖先)を求める過程で深さ探索木に対する処理により、経過した割れ目の数を記録して減算する.
注意事項:
1、データが比較的大きいので、一度プラスしながらTarjanで1回のカット数を求めるのは現実的ではなく、問題に合わない.ある2つの点の間にもともと1つの辺があったので、今もう1つ追加します.このような状況では彼ら2人の間には縁が切れていない.
2、DFN[U]3、LCAを求めるにはテンプレートがありませんが、木を作る必要があります.これでLCAを求めることができます.
コードは次のとおりです.
1つの連通図Gに、ある辺を加えた後の図にどれだけの割れ目があるかを聞く.
問題解決の考え方:
1.Tarjanアルゴリズムを用いてすべてのエッジと各点の親ノードを求め、記録する.各ノードを記録する親ノードは、深いツリーを形成することができます.
2.LCA(最近の公的祖先)を求める過程で深さ探索木に対する処理により、経過した割れ目の数を記録して減算する.
注意事項:
1、データが比較的大きいので、一度プラスしながらTarjanで1回のカット数を求めるのは現実的ではなく、問題に合わない.ある2つの点の間にもともと1つの辺があったので、今もう1つ追加します.このような状況では彼ら2人の間には縁が切れていない.
2、DFN[U]
コードは次のとおりです.
#include <stdio.h>
#include <string.h>
const int MAXN=100005;
struct node
{
int to,next;
} edge[MAXN*4];
int head[MAXN],dfn[MAXN],low[MAXN],pre[MAXN],vis[MAXN],n,m,time,cnt,cut;
bool bi[MAXN];
void init()
{
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
for(int i=0; i<=n; pre[i]=i,i++);
memset(bi,0,sizeof(bi));
cnt=0;
cut=0;
time=1;
}
int min(int a,int b)
{
if(a>b)a=b;
return a;
}
void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
cnt++;
}
void dfs(int u,int fa)
{
dfn[u]=time;
low[u]=time;
time++;
vis[u]=1;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
dfs(v,u);
pre[v]=u; //
low[u]=min(low[u],low[v]);
if(low[v] > dfn[u]) // low
{
cut++;
bi[v] = true;
}
}
else if(vis[v] == 1 && v != fa)
{
low[u]=min(low[u],dfn[v]);
}
}
vis[u]=2;
}
int judge(int u,int v)
{
int cnt1=0;
while(dfn[u]>dfn[v])
{
if(bi[u])
{
cnt1++;
bi[u]=false;
}
u=pre[u];
}
while(dfn[u]<dfn[v])
{
if(bi[v])
{
cnt1++;
bi[v]=false;
}
v=pre[v];
}
while(u!=v)
{
if(bi[u])
{
bi[u]=false;
cnt1++;
}
if(bi[v])
{
bi[v]=false;
cnt1++;
}
u=pre[u];
v=pre[v];
}
return cnt1;
}
int main()
{
int u,v,q,in=0;
while(scanf("%d%d",&n,&m),n+m)
{
if(in)
{
puts("");
}
in++;
init();
for(int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
u--;
v--;
addedge(u,v); //ÎÞÏòͼ¼ÓË«Ïò±ß
addedge(v,u);
}
dfs(0,0);
scanf("%d",&q);
printf("Case %d:
",in);
for(int i=0; i<q; i++)
{
scanf("%d%d",&u,&v);
u--;
v--;
cut-=judge(u,v);
printf("%d
",cut);
}
}
return 0;
}