核心代碼：
int find(int x){ while(x != root[x])/*循環尋找x對應根的值*/ { x = root[x]; } return x;}void unio(int a, int b)/*合并a所在的樹的根，和b所在的樹的根*/{ int x, y; x = find(a);/*求a的根*/ y = find(b);/*求b的根*/ if(x != y) { root[y] = x;/*讓y的根等于x*/ }}題目：小鑫的城堡http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestPRoblem/cid/2014/pid/2798.html
#include<stdio.h>#include<stdlib.h>#include<string.h>int root[100555], flag;int house[100555];int find(int x){ while(x != root[x]) { x = root[x]; } return x;}void unio(int a, int b){ int x, y; x = find(a); y = find(b); if(x != y) { root[y] = x; } else flag = 0;//判斷是否回路}int max1(int a, int b){ if(a < b) return b; else return a;}int main(){ int m, a, b, i, max, num; while(~scanf("%d", &m)) { max = 0; num = 0; memset(house, 0, sizeof(house)); flag = 1; for(i = 1; i <= 100005; i++)//初始化根 root[i] = i; for(i = 0; i < m; i++) { scanf("%d %d", &a, &b); if(max < max1(a, b))//找出最大房間號 max = max1(a, b); house[a]++; house[b]++; unio(a, b);//合并 } for(i = 1; i <= max; i++) { if(house[i]) num++;//統計房間數 } if(flag && num == m + 1) printf("Yes/n");//圖滿足房間數等于路徑數加一 && 不允許有回路 else printf("No/n"); } return 0;}新聞熱點
疑難解答
