POJ 3177——Redundant Paths——————【加边形成边双连通图】

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn = 5100;
struct Edge{
    int from,to,dist,next;
    Edge(){}
    Edge(int _to,int _next):to(_to),next(_next){}
}edges[maxn*4];     //无向图的边
int head[maxn], tot;    //邻接表
int dfs_clock, dfn[maxn];   //时间戳
//Stack:存放边双连通节点、instack:在栈中、ebccno:节点所在分量编号、ebcc_cnt分量数目(从1开始编号)
int Stack[maxn], instack[maxn], top, ebccno[maxn], ebcc_cnt;
int deg[maxn];//记录缩点的度
void init(){
    tot = 0;
    dfs_clock = 0;
    top = 0;
    ebcc_cnt = 0;
    memset(deg,0,sizeof(deg));
    memset(head,-1,sizeof(head));
}
void AddEdge(int _u,int _v){
    edges[tot] = Edge(_v,head[_u]);
    head[_u] = tot++;
}
int dfs(int u,int fa){      //这里的fa是记录的边的编号，用来处理重边
    int lowu = dfn[u] = ++dfs_clock;
    Stack[++top] = u;   //将每个访问的结点放入栈中
   // instack[u] = 1;
    for(int i = head[u]; i != -1; i = edges[i].next){
        int v = edges[i].to;
        if(!dfn[v]){    //如果v没有访问过
            int lowv = dfs(v,i);    //v及v的后代能访问到的最远祖先
            lowu = min(lowu,lowv);  //用后代来更新lowu
        //如果v已经在栈中了，并且这条边不是回边(一条无向边，拆成了有向边，回指了父亲的这条有向边)
        }else if(dfn[v] < dfn[u] && (fa^1) != i){   //有人在这里用instack[v]替代了判断已经在栈中
            lowu = min(lowu,dfn[v]);    //用反向边更新lowu
        }
    }
    if(dfn[u] == lowu){     //找到一个边双连通分量
        ebcc_cnt++;
        for(;;){
            int v = Stack[top--];   
         //   instack[v] = 0;       
            ebccno[v] = ebcc_cnt;   //把节点划分到分量中
            if(u == v){
                break;
            }
        }
    }
  //  low[u] = lowu;
    return lowu;
}
void find_ebcc(int n){
    memset(dfn,0,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            dfs(i,-1);
        }
    }
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        int a,b;
        for(int i = 0; i < m; i++){
            scanf("%d%d",&a,&b);
            AddEdge(a,b);
            AddEdge(b,a);
        }
        find_ebcc(n);
        for(int i = 1; i <= n; i++){
            for(int j = head[i]; j != -1; j = edges[j].next){
                int v = edges[j].to;
                if(ebccno[i] != ebccno[v]){
                    deg[ebccno[v]]++;
                }
            }
        }
        int leaf = 0;
        for(int i = 1; i <= ebcc_cnt; i++){
            if(deg[i] == 1){
                leaf++;
            }
        }
        printf("%d\n",(leaf+1)/2);
    }
    return 0;
}