POJ 3713 Transferring Sylla （三连通图）

【题目大意】

　　给出一个图判断是不是三连通图，三连通图的意思是对于图中任意两点，
　　至少有三条路是可以相互连通的。

【题解】

　　我们可以枚举一个点去掉，然后判断图中是否存在割点，如果存在，
　　则说明这不是个三连通分图，否则则说明是三连通分图。

【代码】

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N=510;
vector<int> G[MAX_N];
int a,n,low[MAX_N],dep[MAX_N],col[MAX_N],m,root,b;
bool flag=0;
int dfs(int u,int fa,int t){
    col[u]=1;
    dep[u]=low[u]=t;
    int tol=0,i,v;
    for(int i=0;i<G[u].size();i++){
        v=G[u][i];
        if(col[v]==2)continue;
        if(col[v]==0){
            dfs(v,u,t+1);
            tol++;
            low[u]=min(low[u],low[v]);
            if(u==root&&tol>1||u!=root&&low[v]>=dep[u]){
                flag=1;
            }
        }else if(col[v]==1&&v!=fa){
            low[u]=min(low[u],dep[v]);
        }
    }return 0;
}
int solve(){
    flag=0;
    for(int i=0;i<n;i++)G[i].clear();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        memset(col,0,sizeof(col));
        memset(dep,0,sizeof(dep));
        memset(low,0,sizeof(low));
        col[i]=2; root=0;
        if(i==0)root=1;
        dfs(root,-1,1);
        for(int j=0;j<n;j++){
            if(col[j]==0){flag=1;break;}
        }if(flag==1)break;
    }if(flag)puts("NO");
    else puts("YES");
}
int main(){
    while(~scanf("%d%d",&n,&m),n+m)solve();
    return 0;
}

POJ 3713 Transferring Sylla （三连通图）

相关推荐