题目链接：https://pta.patest.cn/pta/test/1342/exam/4/question/21732
#include "iostream"
#include "algorithm"
using namespace std;
int father[10001], n;
/* 合并思路：
1.要将小子树合并到大子树上 反过来合并 树会退化成单链表 导致查询时间变为线性时间 从而导致超时
2. 可以采用按节点数大小合并 也可以按树高进行归并（树高变化当且仅当进行归并的2个树高度相同）
3. 本题采用按节点数进行归并
4. 路径压缩 （防止测试数据总是从叶子节点查询 导致O(n*log(n))的查询时间复杂度）
*/
void Init() {
for (int i = 1; i <= n; i++)
father[i] = -1; /* 初始化为当前树的节点数的相反数 */
}
int Find(int x) { /* 查询根节点 */
if (father[x] <= -1)
return x;
else
return father[x] = Find(father[x]); /* 路径压缩 */
} void Union(int x, int y) {
x = Find(x);
y = Find(y);
if(father[x] < father[y]){ /* 按节点数大小进行归并 */
father[x] += father[y];
father[y] = x;
n--; /* 2个集合归并 总集合数减一*/
}
else {
father[y] += father[x];
father[x] = y;
n--;
}
}
int main() {
char ch;
int i, j;
cin >> n;
Init();
bool flag = true;
while (cin >> ch) { //cout << ch << endl;
if (ch == 'S') {
if (n == 1)
cout << "The network is connected." << endl;
else
cout << "There are " << n << " components." << endl;
break;
}
cin >> i >> j;
switch (ch) {
case 'C':
if (Find(i) == Find(j)) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
break;
case 'I':Union(i, j); break;
}
}
return 0;
}
