poj3694 (구교+LCA 문제)

Network
Time Limit: 5000MS
 
Memory Limit: 65536K
Total Submissions: 3868
 
Accepted: 1321
Description
A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers. The administrator finds that some links are vital to the network, because failure of any one of them can cause that data can't be transformed between some computers. He call such a link a bridge. He is planning to add some new links one by one to eliminate all bridges.
You are to help the administrator by reporting the number of bridges in the network after each new link is added.
Input
The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤ 200,000). Each of the following M lines contains two integers A and B ( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B. Computers are numbered from 1 to N. It is guaranteed that any two computers are connected in the initial network. The next line contains a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links the administrator plans to add to the network one by one. The i-th line of the following Q lines contains two integer A and B (1 ≤ A ≠ B ≤ N), which is the i-th added new link connecting computer A and B. The last test case is followed by a line containing two zeros.
Output
For each test case, print a line containing the test case number( beginning with 1) and Q lines, the i-th of which contains a integer indicating the number of bridges in the network after the first i new links are added. Print a blank line after the output for each test case.
Sample Input

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

Sample Output

Case 1:
1
0

Case 2:
2
0

Source
2008 Asia Hefei Regional Contest Online by USTC
제목:http://poj.org/problem?id=3694
분석: 이 문제는 처음부터 다리를 구하고 LCA(최소 공공조상)로 해결하려고 했지만 본인이 비교적 좌절했기 때문에 LCA가 익숙하지 않아서 간단한 방법을 생각해 냈지만 하지 못했다. 방법은 일반적으로 두 가지가 있다.
첫 번째: 이해하기 쉽다. 절단 효율이 비교적 높은 것은 일반적으로 모든 변두리 연결 블록을 구하여 하나의 점으로 축소한다. 그러면 원도는 나무가 된다. 물어볼 때마다 두 개의 점에 대응하는 새로운 점을 찾아서 그들과 그들의 LCA 사이에 몇 개의 변두리가 있는지 보고 총 변수-s를 구한 다음에 세 개의 점을 직접 모든 점으로 다시 축소한다. 이렇게 하면 실현되기는 정말...
두 번째: 다리를 구하는 동시에 그림을 층으로 나누었다. 우리는 새로운 그림을 구성할 필요가 없다. 원도에서 정리에 따라 하면 된다. 절단된 점(뒤에 흐르는 것), 그리고 모든 점의 반향 변(즉 그 변을 통해 흐르는 것)을 기록한다. 그러면 두 점을 물어볼 때마다 먼저 그들을 같은 층으로 옮긴 다음에 두 점이 공통점인지 아닌지를 판단한다. 만약에 두 점이 동시에 위로 이동하지 않고 공통점까지 옮긴다.이동 중 다리로 표시된 점을 만나면 답을 줄이고 표시를 바꾸면 된다...
두 번째 해법이 지나치면 다행이다. 만약에 이 문제에 데이터 한 조가 나타나서 이 그림이 일직선이 되고 머리와 끝을 물어볼 때마다 복잡도가 (QV)로 올라가면 정말 무섭다~~~
내일 첫 번째 수법 보충, 곤란
그래, 사실 어제 두 번째를 최적화하기 위해 유사한 방법을 생각해 봤는데 좌절했어. 오늘 자세히 보니 저급한 오류였어...
LCA를 검사할 때 경로의 점을 기록하면 그들의 부모 노드를 모두 LCA, 시간 290++ms로 바꾸면 기분이 좋다
코드(
빨간색 부분은 변경 부분):

#include<cstdio>
#define min(a,b) (a<b?a:b)
using namespace std;
const int mm=444444;
const int mn=111111;
int t[mm],p[mm];
int h[mn],pre[mn],dfn[mn],low[mn];
bool bg[mn];
int i,j,k,n,m,q,top,idn,sum,cas=0;
void dfs(int u)
{
    dfn[u]=low[u]=++idn;
    for(int i=h[u],v;i>=0;i=p[i])
        if(!dfn[v=t[i]])
        {
            pre[v]=u,dfs(v);
            low[u]=min(low[u],low[v]);
             if(dfn[u]<low[v])++sum,bg[v]=1;
        }
        else if(v!=pre[u])low[u]=min(low[u],dfn[v]);
}
void tarjan()
{
    for(int i=0;i<=n;++i)dfn[i]=bg[i]=0;
    idn=sum=0,dfs(1);
}
void move(int &x)
{
    if(bg[x])--sum,bg[x]=0;
    p[top++]=(x=pre[x]);// 
}
int lca(int x,int y)
{
    p[0]=x,p[1]=y,top=2;// 
    while(x!=y)
    {
        if(dfn[x]>dfn[y])move(x);
        else if(dfn[x]<dfn[y])move(y);
        else move(x),move(y);
    }
    while(top--)if(p[top]!=x)pre[p[top]]=x;// 
    return sum;
}
int main()
{
    while(scanf("%d%d",&n,&m),n+m)
    {
        for(i=k=0;i<=n;++i)h[i]=-1;
        while(m--)
        {
            scanf("%d%d",&i,&j);
            t[k]=j,p[k]=h[i],h[i]=k++;
            t[k]=i,p[k]=h[j],h[j]=k++;
        }
        tarjan();
        scanf("%d",&q);
        printf("Case %d:
",++cas);
        while(q--)
        {
            scanf("%d%d",&i,&j);
            printf("%d
",lca(i,j));
        }
        puts("");
    }
    return 0;
}