hihocoder1184(邊的雙聯通分量)

連結：點選打開連結

題意：給出n個點m條邊的無向圖，輸出邊的雙聯通分量的個數，并輸出每個點所在的雙聯通分量中最小的點的編号

代碼：

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int siz=20005;
int dfn[siz],low[siz],vis[siz],sig[siz*5];
struct node{
    int to,id;
};
vector<node> G[siz];
void dfs(int S,int fa,int &id){
    int i,tmp;
    vis[S]=1;
    dfn[S]=low[S]=id++;
    for(i=0;i<G[S].size();i++){
        tmp=G[S][i].to;
        if(vis[tmp]==0){
            dfs(tmp,S,id);
            low[S]=min(low[S],low[tmp]);
            if(low[tmp]>dfn[S])
            sig[G[S][i].id]=1;                  //标記哪條邊是橋
        }
        else if(tmp!=fa)
        low[S]=min(low[S],dfn[tmp]);
    }
}
void cal(int S,int id){
    int i,tmp;
    vis[S]=id;
    for(i=0;i<G[S].size();i++){
        tmp=G[S][i].to;
        if(sig[G[S][i].id]||vis[tmp])
        continue;
        cal(tmp,id);
    }
}
int main(){
    int n,m,i,j,u,v,id;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++){                      //去掉橋之後剩下的每個區域都是一個邊的
            vis[i]=0;                           //雙聯通分量
            G[i].clear();
        }
        for(i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back((node){v,i});
            G[v].push_back((node){u,i});
        }
        id=1;
        memset(sig,0,sizeof(sig));
        dfs(1,-1,id);
        id=0;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++){
            if(vis[i]==0){
                id++;
                cal(i,i);                       //标記橋之後再dfs一遍找出邊的雙聯通分量
            }
        }
        printf("%d\n",id);
        for(i=1;i<=n;i++){
            if(i!=1)
            printf(" ");
            printf("%d",vis[i]);
        }
        printf("\n");
    }
    return 0;
}