解题思路:
注意事项:
参考代码:
#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语言程序设计教程(第三版)课后习题7.1 (C++代码)浏览:683 |
C二级辅导-计负均正 (C语言代码)浏览:1192 |
C语言训练-求素数问题 (C语言代码)浏览:953 |
C语言训练-自守数问题 (C语言代码) long long浏览:1061 |
陶陶摘苹果 (C语言代码)浏览:1604 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:758 |
C语言训练-排序问题<2> (C++代码)浏览:880 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:470 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:885 |
【简单计算】 (C语言代码)浏览:622 |