首页 > 代码库 > 【hihoCoder第十四周】无间道之并查集

【hihoCoder第十四周】无间道之并查集

2024-07-25 22:45:04   220人阅读

就是基础的并查集。0代表合并操作，1代表查询操作。一开始以为会卡路径压缩，忐忑的交了一版裸并查集，结果AC了。数据还是很水的。

以后坚持做hiho，当额外的练习啦~

 

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 map<string, int> Hash; 5 int Father[1000005]; 6  7 int getFather (int x) { 8     if (x != Father[x]) { 9         return getFather (Father[x]);10     }11     return x;12 }13 14 void Union (int p, int q) {15     int x = getFather (p);16     int y = getFather (q);17     if (x != y) {18         Father[y] = x;19     }20 }21 22 int main () {23     ios :: sync_with_stdio(false);24     cin.tie(0);25     int n, a, cnt = 1;26     string x, y;27     cin >> n;28     for (int i = 0; i < 100005; ++ i) {29         Father[i] = i;30     }31     while (n --) {32         cin >> a >> x >> y;33         if (a == 0) {34             if (!Hash[x]) {35                 Hash[x] = cnt ++;36             }37             if (!Hash[y]) {38                 Hash[y] = cnt ++;39             }40             Union (Hash[x], Hash[y]);41         } else {42             if (!Hash[x]) {43                 Hash[x] = cnt ++;44             }45             if (!Hash[y]) {46                 Hash[y] = cnt ++;47             }48             if (getFather (Hash[x]) == getFather (Hash[y])) {49                 cout << "yes" << endl;50             } else {51                 cout << "no" << endl;52             }53         }54     }55     return 0;56 }

 

【hihoCoder第十四周】无间道之并查集


联系
我们