HDU 3390 Railway 邊雙連通分量

題目描述: There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build. Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen. Input: The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v. You can assume that there is no loop and no multiple edges. The last test case is followed by two zeros on a single line, which means the end of the input. Output: Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample. sample Input: 8 100 11 22 33 03 44 55 66 77 45 70 0 Output: 1 5   由題目意思，圖中的橋是無用的，那些雙連通分量中的邊多于節點多，就全是沖突邊。

/*
 * @author ipqhjjybj
 * @date  20130622
 */
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>

#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <memory.h>
using namespace std;

#define inf 0x3f3f3f3f
#define MAXN 10007
#define MAXM 100010
#define clr(x,k) memset((x),(k),sizeof(x))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct Edge{
    int st,ed;
    Edge(){};
    Edge(int a,int b){
        st = a,ed = b;
    }
};
int n,m;
vector<int> viMap[MAXN];
vector<Edge> block[MAXN];
stack<Edge> sEtack;
int low[MAXN],dfn[MAXN],vs[MAXN];
int tcc,sig;
int ans1,ans2;
void init(){
    int a,b;
    for(int i = 0;i <= n;i++) viMap[i].clear(),block[i].clear();
    for(int i = 0;i < m;i++){
        scanf("%d %d",&a,&b);
        viMap[a].push_back(b);
        viMap[b].push_back(a);
    }
    clr(low,0);
    clr(dfn,0);
    ans1 = ans2 = sig = tcc = 0;
    while(!sEtack.empty()) sEtack.pop();
}
int Tarjan(int cur,int &sig,int &tcc,int from){
    low[cur] = dfn[cur]=++sig;
    for(vector<int>::iterator it = viMap[cur].begin();it != viMap[cur].end();it++){
            if(!dfn[*it]){
                sEtack.push(Edge(cur,*it));
                Tarjan(*it,sig,tcc,cur);
                low[cur]=min(low[cur],low[*it]);
                if(dfn[cur]<=low[*it]){   // cur<*it 是一個橋, 當dfn[cur]==low[*it]時，說明這是個連通的回路
                    for(Edge temp;!sEtack.empty();){   //sEtack.empty() 棧不可能為空。理論上不會用到
                        temp = sEtack.top();
                        if(dfn[temp.st]<dfn[*it]) break; //說明temp.st在*it之前被周遊到，放進棧中的是那些與由*it查詢到的邊,即*it的子樹(子樹中的那些連通向量在之前已在搜尋中被排除)
                                                // 也為了防止重複壓棧
                        block[tcc].push_back(temp);sEtack.pop();
                    }
                    block[tcc++].push_back(Edge(cur,*it));
                    sEtack.pop();
                    if(dfn[cur]<low[*it]) ans1++; // (cur,*it) 是一個橋,橋是無用的，記錄
                }
            }else if(*it != from && dfn[*it]<dfn[cur]){  //因為建立在深搜之上
                low[cur] = min(low[cur],dfn[*it]);
                sEtack.push(Edge(cur,*it));
            }
    }
    return 0;
}
int main(){
    //freopen("3394.in","r",stdin);
    while(scanf("%d %d",&n,&m)){
        if(!n&&!m)
            break;
        init();
        for(int i = 0;i < n;i++)
            if(!dfn[i])
                Tarjan(i,sig,tcc,-1);
        for(int i = 0;i < tcc;i++){
            clr(vs,0);
            int temp=0;
            for(int j = 0;j < block[i].size();j++){
                if(!vs[block[i][j].st]) vs[block[i][j].st]=1,temp++;
                if(!vs[block[i][j].ed]) vs[block[i][j].ed]=1,temp++;
            }
            if(temp<block[i].size()) ans2+=block[i].size();
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}