并查集問(wèn)題。給出n個(gè)點(diǎn)n對(duì)連接關(guān)系

我們需要判斷它是否能夠構(gòu)成一個(gè)類似圓的圖形（帶邊的封閉圖形）

這個(gè)時(shí)候我們需要用并查集

并查集記得加路徑優(yōu)化

我們需要知道封閉圖形每個(gè)點(diǎn)只能與兩個(gè)點(diǎn)相連。

而且這個(gè)封閉圖形由n個(gè)點(diǎ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];//每次建立新的聯(lián)系祖先點(diǎn)都需要將分支點(diǎn)的所包含的子點(diǎn)數(shù)加起來(lái)
        f[yy]=xx;    }}
//我們需要記錄每個(gè)點(diǎn)出現(xiàn)的次數(shù)
//我們需要借助祖先點(diǎn)
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");    }}