题目链接
https://www.patest.cn/contests/gplt/L2-024
题意 给出 几个不同的圈子，然后 判断 有哪些人 是属于同一个部落的，或者理解为 ，有哪些人 是有关系的， 朋友的朋友 也属于同一个部落
思路 用并查集 并，然后最后查一下 有几个连通块，就可以输出有几个互不相交的部落，然后最后判断两个人是否是同一部落的，只要查找一下两个人是否属于同一祖宗就可以
AC代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e4 + 5; const int MOD = 1e9 + 7; int pre[maxn], arr[maxn]; int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; pre[x] = r; return r; } void join(int x, int y) { int fx = find(x), fy = find(y); if (x != fy) pre[fx] = fy; } int main() { int n, mi; int num, vis; cin >> n; int i, j, k = 0; map <int, int> q; map <int, int> m; map <int, int> flag; flag.clear(); m.clear(); q.clear(); for (i = 0; i < maxn; i++) pre[i] = i; for (i = 0; i < n; i++) { cin >> mi; cin >> num; flag[num] = 1; for (j = 1; j < mi; j++) { scanf("%d", &vis); join(num, vis); flag[vis] = 1; } } map <int, int>::iterator it; for (it = flag.begin(); it != flag.end(); it++) arr[k++] = it -> first; int len = k; for (i = 0; i < k; i++) q[find(arr[i])] = 1; cout << len << " " << q.size() << endl; scanf("%d", &mi); for (i = 0; i < mi; i++) { int a, b; scanf("%d%d", &a, &b); if (find(a) == find(b)) printf("Y\n"); else printf("N\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433303.html
