zoj Circle

并查集问题。给出n个点n对连接关系

我们需要判断它是否能够构成一个类似圆的图形（带边的封闭图形）

这个时候我们需要用并查集

并查集记得加路径优化

我们需要知道封闭图形每个点只能与两个点相连。

而且这个封闭图形由n个点组成

Your task is so easy. I will give you an undirected graph, and you just need to tell me whether the graph is just a circle. A cycle is three or more nodes V₁, V₂, V₃, ... V_k, such that there are edges between V₁ and V₂, V₂ and V₃, ... V_k and V₁, with no other extra edges. The graph will not contain self-loop. Furthermore, there is at most one edge between two nodes.

There are multiple cases (no more than 10).

The first line contains two integers n and m, which indicate the number of nodes and the number of edges (1 < n < 10, 1 <= m < 20).

Following are m lines, each contains two integers x and y (1 <= x, y <= n, x != y), which means there is an edge between node x and node y.

There is a blank line between cases.

If the graph is just a circle, output "YES", otherwise output "NO".

3 31 22 31 34 41 22 33 11 4
Sample Output
YESNO上代码
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<iostream>#include<ctype.h>#include<stack>#include<queue>using namespace std;int f[1003],num[1003],ans[1003];int join(int x){    return (x==f[x])?x:join(f[x]);//并查集的查，外加路径压缩}void coin(int x,int y)//并{    int xx=join(x);    int yy=join(y);    if(xx!=yy)    {        ans[xx]+=ans[yy];//每次建立新的联系祖先点都需要将分支点的所包含的子点数加起来
        f[yy]=xx;    }}
//我们需要记录每个点出现的次数
//我们需要借助祖先点
int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        int flag=0;        memset(num,0,sizeof(num));        for(int i=1; i<=n; i++)f[i]=i,ans[i]=1;        int a,b;        for(int i=0; i<m; i++)        {            scanf("%d%d",&a,&b);            if(a==b)            {                flag=1;            }            num[a]++;            num[b]++;            coin(a,b);        }        for(int i=1; i<=n; i++)        {            int z=join(i);            if(num[i]!=2||ans[z]!=n)            {                //PRintf("%d %d/n",i,ans[z]);                flag=1;                break;            }        }        if(flag)            printf("NO/n");        else printf("YES/n");    }}