今天看科目四的题目明天去考试
#include<stdio.h> #include<stdlib.h> #include<string.h> #define max 10005 int n, k, q; // n:已知小圈子的个数 k:小圈子里的人数 q:查询次数 int x, y; // x:第一个人代表小圈子 y:小圈子的其他人 int i, j, l; // 遍历 int cnt1 = 0, cnt2 = 0; // cnt1:社区的总人数 cnt2:互不相交的部落的个数 int a, b; // 一对被查询的人的编号 int cnt[max]; // 部落数组 int pre[max]; // 并查集数组 void init(); int find(int x); void Union(int a, int b); int main() { // 初始化 memset(cnt, 0, sizeof(cnt)); init(); scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d %d", &k, &x); cnt[x] = 1; for (j = 1; j < k; j++) { scanf("%d", &y); cnt[y] = 1; Union(x, y); } } // 求 社区的总人数 和 互不相交的部落的个数 for (i = 0; i < max; i++) { // cnt[i]不为0，说明i存在，及人数+1 if (cnt[i]) { cnt1++; // pre[i] == i 说明改部落未与其他部落互通 if (pre[i] == i) cnt2++; } } printf("%d %d\n", cnt1, cnt2); scanf("%d", &q); for (i = 0; i < q; i++) { scanf("%d %d", &a, &b); if (find(a) == find(b)) printf("Y\n"); else printf("N\n"); } return 0; } void init() { for (int i = 0; i < max; i++) { pre[i] = i; } } int find(int x) { if (x == pre[x]) return x; return pre[x] = find(pre[x]); } void Union(int a, int b) { if (b == -1) return; int f_a = find(a); int f_b = find(b); if (f_a != f_b) { pre[f_a] = f_b; } }