【并查集】ZOJ Problem Set – 3321 Circle

Circle

Time Limit: 1 Second      Memory Limit: 32768 KB

---

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.

Input

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.

Output

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

Sample Input

3 3
1 2
2 3
1 3

4 4
1 2
2 3
3 1
1 4

Sample Output

YES
NO

成环条件：所有点度数小于等于2（度数判定），且只有一个连通分支（并查集）

#include<iostream>
#include<cstdio>
using namespace std;
int num[21];
int used[21];
int du[21];
int Find(int x)
{
  int r=x;
  while(r!=num[r])
    r=num[r]; 
  int i=x,j;
  while(num[i]!=r)//路径优化
  {
    j=num[i];
    num[i]=r;
    i=j;
  }
  return r;
}
void mix(int x,int y)
{
  int fx=Find(x),fy=Find(y);
  if(fx!=fy)
  {
    num[fy]=fx;
  }
}

int main()
{
 int n, m;
 while(cin>>n>>m)
 {
    int i;
    int x, y;
    for(i = 1; i <= n; i++)
    {
       num[i] = i;
       used[i] = 0;
       du[i] = 2;
    }
    int flag = 0;
    int boy_graph_num = 0;
    for(int i = 1; i <= m; i++)
    {
       cin>>x>>y;
       used[x] = 1;
       used[y] = 1;
       du[x]--;
       du[y]--;
       int a = Find(x);
       int b = Find(y);
       if(a != b)
        mix(a, b);
       else
       { 
        boy_graph_num++;
       }
       if(boy_graph_num == 1)
         for(int j = 1; j <= n; j++)
           if( du[j] < 0)
           {
            flag = 1;
            break;
           }
    }
  
    if(boy_graph_num == 1 && flag == 0)
     puts("YES");
    else
     puts("NO");
  

 }
}