Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 39392 Accepted Submission(s): 12092
Problem Description 上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。
# include <iostream> # include <stdio.h> # include <string.h> # include <algorithm> const int M= 1005; const int MAX= 100005; const long long int MOD=1000000007; using namespace std; int pre[MAX]; int vis[MAX]; int ans,cnt; void ff(int n) { for(int i=0; i<MAX; i++) { pre[i]=i; vis[i]=0; } return ; }
int findi(int x) { int r=x; while(r!=pre[r]) r=pre[r];
int i=x,j; //路径压缩 while(i!=j) { j=pre[i]; pre[i]=r; i=j; }
return r; }
int join(int x,int y) { int fx=findi(x),fy=findi(y); if(fx!=fy) pre[fx]=fy; else ans=0; //.在连接两个点的时候 如果这两个点的父节点相同 那 再进行连接这两个点的操作 就会产生回路. }