解题思路：给定n个点，m条边，判断是否构成一个环

注意到构成一个环，所有点的度数为2，即一个点只有两条边与之相连，再有就是判断合并之后这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.

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 31 22 31 34 41 22 33 11 4

Sample Output

YESNO

#include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  using namespace std;int degree[10010],pre[10010];int find(int root){ return root == pre[root] ? root : pre[root] = find(pre[root]); }void unionroot(int x,int y){	int root1=find(x);	int root2=find(y);	if(root1!=root2)	pre[root1]=root2;}int main(){	int m,n,u,v,i,j;	while(scanf("%d %d",&n,&m)!=EOF)	{		int flag=1;		memset(degree,0,sizeof(degree));		for(i=1;i<=10010;i++)		pre[i]=i;		for(i=1;i<=m;i++)		{			scanf("%d %d",&u,&v);			degree[u]++;			degree[v]++;			unionroot(u,v);			}				for(i=1;i<=n;i++)		{			if(degree[i]!=2)			{				flag=0;				break;			}			if(find(i)!=find(n))			{				flag=0;				break;			}		}		if(flag)		printf("YES\n");		else		printf("NO\n");			}}

ZOJ 3321 Circle【并查集】