題目大意： ?????????? 讓你輸入n,m,代表一個迷宮中的兩個點，要求這個迷宮中，不能有回路。這是一個無向圖，但是其實根據題意來說，最終應該是一棵樹。 解題思路： ?????????? 只要輸入的時候一開始判斷兩個點的父節點是不是相同的，如果相同，那么說明這兩個點是連通的，你再加上去，就證明要產生回路啦。所以要排除，，還有，當輸入n,m為0時，這時候輸出yes,最后再判斷下，這個圖有沒有連通分量就可以了。。。 #include #include using namespace std; const int MAX=100005; int pre[MAX]; int visited[MAX]; int find(int x) { int r, j; r = x; while(pre[r] != r) { r = pre[r]; } while(pre[x] != r) //優化{ j = pre[x];//從底部，一個一個判斷上去，如果有一個父節點不是根節點，那么就將它放在根節點上pre[x] = r; x = j;} return r; } //int find(int x) //{ // // int r=x; // // while(pre[r]!=r) // // r=pre[r]; // // return r; //} //void merge(int x,int y) //{ // // int fx,fy; // // fx=find(x); // // fy=find(y); // // if(fx!=fy) // // pre[fx]=fy; //}int main(void) {int n, m, f1, f2;while(scanf("%d%d", &n,&m)==2){memset(visited,0,sizeof(visited));for(int i = 1; i < MAX; i++) pre[i] = i;if (n == -1 && m == -1 )break;if (n == 0 && m == 0 ){ printf("Yes\n");continue;}f1 = find(n); f2 = find(m); pre[f1]=f2;visited[n]=visited[m]=1;int minn=200005,maxn=0,flag=0;if ( n< minn ) minn = n; //找到輸入 的所有數據中最小的和最大的便于減小最后數組遍歷時的復雜度 if ( m < minn ) minn = m;if ( n> maxn ) maxn = n;if ( m > maxn ) maxn = m;while(scanf("%d%d", &n,&m)) { if ( n== 0 && m == 0)break; if ( n< minn ) minn = n; //找到輸入 的所有數據中最小的和最大的便于減小最后數組遍歷時的復雜度 if ( m < minn ) minn = m;if ( n> maxn ) maxn = n;if ( m > maxn ) maxn = m;visited[n]=visited[m]=1;f1 = find(n); f2 = find(m); if(f1==f2){flag=1;}else{pre[f1]=f2;}} if(flag==1)printf ("No\n");if (flag==0){for (int i = minn; i <= maxn; i++){if ( visited[i] && pre[i] == i )flag++;}if (flag == 1)printf ("Yes\n");elseprintf ("No\n");} } return 0; }

轉載于:https://www.cnblogs.com/cchun/archive/2011/11/09/2520177.html

總結

以上是生活随笔為你收集整理的HDU1272_并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。