ZOJ 3321 Circle(并查集)

ZOJ 3321 Circle(并查集)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3321

题意:

给你一个n节点m条边的无向图,问你该图是否正好是一个环?

分析:

无向图是一个简单环 充要条件是 所以节点的度数==2且图连通.

所以我们只需要记录每个节点的度且用并查集判断每个节点分别属于哪些连通分量即可.

AC代码:

#include<cstdio>
using namespace std;
const int maxn=100+5;
int degree[maxn];
int fa[maxn];
int findset(int x)
{
    return fa[x]==-1?x:fa[x]=findset(fa[x]);
}
void bind(int i,int j)
{
    int fi=findset(i);
    int fj=findset(j);
    if(fi!=fj)
    {
        fa[fi]=fj;
    }
}
bool ok(int n)
{
    for(int i=1;i<=n;++i)
        if(degree[i]!=2) return false;
    int root=fa[1]==-1?1:fa[1];
    for(int i=2;i<=n;++i)
        if(findset(i)!=root) return false;
    return true;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=1;i<=n;++i)
        {
            degree[i]=0;
            fa[i]=-1;
        }
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            ++degree[u];
            ++degree[v];
            bind(u,v);
        }
        printf("%s\n",ok(n)?"YES":"NO");
    }
    return 0;
}