PRoblem Description
从前有一个国王,他叫小鑫。有一天,他想建一座城堡,于是,设计师给他设计了好多简易图纸,主要是房间的连通的图纸。小鑫希望任意两个房间有且仅有一条路径可以相通。小鑫现在把设计图给你,让你帮忙判断设计图是否符合他的想法。比如下面的例子,第一个是符合条件的,但是,第二个不符合,因为从5到4有两条路径(5-3-4和5-6-4)。Input
多组输入,每组第一行包含一个整数m(m < 100000),接下来m行,每行两个整数,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。Output
每组数据输出一行,如果该城堡符合小鑫的想法,那么输出"Yes",否则输出"No"。Example Input
52 52 31 33 64 661 21 33 43 55 66 4Example Output
YesNo#include<stdio.h>#include<string.h>#define maxn 100005int a[maxn];int wz[maxn];void init(){ int i; for(i=0;i<=maxn;i++) { a[i]=i; }}int f(int x){ int i,j; i=x; while(a[x]!=x) { x=a[x]; } while(a[i]!=x) { j=a[i]; a[i]=x; i=j; } return x;}int merge(int u,int v){ int x,y; x=f(u); y=f(v); if(x!=y) { a[x]=y; return 1; } else { return 0; }}int main(){ int m,u,v,t,flag; while(scanf("%d",&m)!=EOF) { init(); flag=t=0; memset(wz,0,sizeof(wz)); while(m--) { scanf("%d%d",&u,&v); if(!wz[u]) { wz[u]=1; t++; } if(!wz[v]) { wz[v]=1; t++; } if(merge(u,v)) { t--; } else { flag=1; } } if(flag||t!=1) { printf("No/n"); } else { printf("Yes/n"); } } return 0;}
新闻热点
疑难解答