HDU 1272 小希的迷宮 並查集判斷樹結構

問題描述

給定無向圖的邊列表（以 0 0 結束），多組測試數據（以空行分隔，-1 -1 結束）。判斷圖是否為樹：連通且無環。輸出 Yes/No。

判斷樹的條件

1. 邊數 = 節點數 - 1（連通圖的必要條件）
2. 無環（並查集檢測）
3. 連通（最終並查集只有 1 個根）

實際上，若無環且邊數 = 節點數 - 1，自動連通。但輸入可能不給出孤立節點，需用 Set 記錄出現過的節點。

並查集處理邊界情況

• 空圖（無邊）：視為 Yes（單節點或空圖均為樹）
• 自環（如 1 1）：成環，輸出 No
• 重複邊：並查集第二次合併時檢測到同集合，判為成環

代碼框架

int parent[100005], rnk[100005];
void init() { for (int i=1;i<100005;++i) parent[i]=i, rnk[i]=0; }
int find(int x) { return parent[x]==x?x:parent[x]=find(parent[x]); }
bool unite(int x, int y) {
    x=find(x); y=find(y);
    if (x==y) return false; // 成環
    if (rnk[x]