lightoj 1291 无向图边双联通+缩点统计叶节点

题目链接：http://lightoj.com/volume_showproblem.php?problem=1291

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 11150;
const int INF = 0x3f3f3f;

int pre[maxn],low[maxn],dfs_clock;

int bccnum[maxn],bcc_cnt;  //记录每个点属于哪个边联通分量；
bool isbridge[maxn*5];     //isbridge[i],边i是不是桥；
int n,m;
int deg[maxn];


struct Edge{
    int u,v;
    int next;
    Edge(int u=0,int v=0,int next=0): u(u),v(v),next(next) {}
}edges[maxn*5];
int head[maxn],cnt ;


void addedge(int u,int v){
    edges[cnt] = Edge(u,v,head[u]);
    head[u] = cnt++;
}

void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}

void tarjan(int u,int fa){
    pre[u] = low[u]  =  dfs_clock++;
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v = edges[i].v;
        if(v == fa)  continue;
        if(!pre[v]){
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > pre[u])  {isbridge[i] = true;  isbridge[i^1] = true;}
        }
        else
            low[u] = min(low[u],pre[v]);
    }
}
void dfs(int u){
    bccnum[u] = bcc_cnt;
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v = edges[i].v;
        if(bccnum[v] || isbridge[i])  continue;
        dfs(v);
    }
}

void find_bcc(){
    bcc_cnt = 0;
    memset(bccnum,0,sizeof(bccnum));
    for(int i=0;i<n;i++){
        if(!bccnum[i]){
            bcc_cnt++;
            dfs(i);
        }
    }
}

void BuildnewG(){
    memset(deg,0,sizeof(deg));
/**    for(int u=0;u<n;u++){
        for(int i=head[u];i!=-1;i=edges[i].next){
            int v = edges[i].v;
            if(bccnum[u] != bccnum[v]){
                deg[bccnum[u]]++;
                deg[bccnum[v]]++;
            }
        }
    }  **/   //两种方法都可以；但下面这种要快些；
    for(int i=0;i<cnt;i+=2){
        if(isbridge[i]){
            deg[bccnum[edges[i].u]]++;
            deg[bccnum[edges[i].v]]++;
        }
    }
}


int main()
{
   // freopen("E:\acm\input.txt","r",stdin);
    int T;
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        dfs_clock = 1;
        memset(pre,0,sizeof(pre));
        memset(isbridge,0,sizeof(isbridge));
        tarjan(0,-1);   //找桥；

        find_bcc();
        BuildnewG();
        int ans = 0;
        for(int i=1;i<=bcc_cnt;i++)
            if(deg[i] == 1)  ans++;    //如果/**...**/中找法，则deg[i] == 2,因为统计了两次。
        if(ans%2)  ans = ans/2+1;
        else       ans = ans/2;
        printf("Case %d: %d
",t,ans);
    }
}