# 【并查集】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


#include<iostream>
#include<cstdio>
using namespace std;
int num;
int used;
int du;
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");

}
}