首页 > 代码库 > Circle
Circle
Circle
| Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
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 V1, V2, V3, ... Vk, such that there are edges between V1 and V2, V2 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 <= 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
Hint
/*判环，每个点给出的时候，会调用两次，每个点的祖先都是一个*/#include<bits/stdc++.h>#define N 50using namespace std;int bin[N];int visit[N];int n,m;int findx(int x){ while(x!=bin[x]) x=bin[x]; return x;}void built(int x,int y){ int fx=findx(x); int fy=findx(y); if(fx!=fy) bin[fx]=fy;}bool ok(){ for(int i=1;i<=n;i++) { //cout<<i<<"="<<visit[i]<<endl; if(visit[i]!=2) return false; } for(int i=2;i<=n;i++) { if(findx(i)!=findx(1)) return false; } return true;}int main(){ //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { memset(visit,0,sizeof visit); for(int i=0;i<n;i++) bin[i]=i; int x,y; while(m--) { scanf("%d%d",&x,&y); visit[x]++; visit[y]++; built(x,y); } if(ok()) puts("YES"); else puts("NO"); }}
Source
Circle