解题思路:
注意事项:
参考代码:
#include <stdio.h> #include <string.h> // 初始化并查集 int *InitUFS(int size) { int *ufs = (int *) malloc(sizeof(int) * (size + 1)); for (int i = 0; i <= size; i++) { // 初始化并查集,每个结点的父结点都是它本身 ufs[i] = i; } return ufs; } // 查找 x 所在集合的根结点 int FindRoot(int *ufs, int x) { for (; x >= 0 && x != ufs[x]; x = ufs[x]); // 从x往上查找其所在集合的根结点 return x; } // 将 x, y 所在的两个集合合并 void UnionSets(int *ufs, int x, int y) { ufs[FindRoot(ufs, y)] = FindRoot(ufs, x); // 找到 y 的根结点,将其合并到 x 的根结点的子集 } int main() { int n, m, xi, yi, x, y, *ufs; scanf("%d %d", &n, &m); ufs = InitUFS(n); while (m--) { scanf("%d %d", &xi, &yi); UnionSets(ufs, xi, yi); } scanf("%d %d", &x, &y); int root1 = FindRoot(ufs, x); int root2 = FindRoot(ufs, y); printf(root1 == root2 ? "Yes\n" : "No\n"); free(ufs); return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:613 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:377 |
母牛的故事 (C语言代码)浏览:930 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:605 |
WU-格式化数据输出 (C语言代码)浏览:1752 |
printf基础练习2 (C语言代码)浏览:617 |
矩阵加法 (C语言代码)浏览:1722 |
1126题解浏览:590 |
模拟计算器 (C++代码)浏览:806 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:509 |