【并查集】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 V1V2V3, ... Vk, such that there are edges between V1 and V2V2 and V3, ... Vk and V1, 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 <= xy <= nx != 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");
  

 }
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

4 × 2 =