#include #include using namespace std;

// 并查集的数据结构 vector father; // 存储每个节点的父节点

// 初始化并查集 void init(int n) { father.resize(n + 1); for (int i = 1; i <= n; i++) { father[i] = i; } }

// 查找根节点 int find(int x) { if (x != father[x]) { father[x] = find(father[x]); } return father[x]; }

// 合并两个部落 void merge(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { father[rootX] = rootY; } }

int main() { int N; cin >> N; // 输入小圈子的个数 init(N); // 初始化并查集 vector<vector> circles(N); // 存储每个小圈子的人 vector count(N); // 存储每个小圈子的人数 for (int i = 0; i < N; i++) { int K; cin >> K; // 输入小圈子里的人数 circles[i].resize(K); for (int j = 0; j < K; j++) { cin >> circles[i][j]; // 输入小圈子里的每个人的编号 count[i]++; } } int Q; cin >> Q; // 输入查询次数 for (int i = 0; i < Q; i++) { int x, y; cin >> x >> y; // 输入被查询的人的编号 // 判断x和y是否属于同一个部落 int rootX = find(x); int rootY = find(y); if (rootX == rootY) { cout << "Y" << endl; } else { cout << "N" << endl; } } // 统计总人数和互不相交的部落个数 int total = 0; int disjoint = 0; for (int i = 1; i <= N; i++) { if (father[i] == i) { disjoint++; } total += count[i-1]; } cout << total << " " << disjoint << endl; return 0; }

C++ 代码实现部落统计和关系查询

原文地址: https://www.cveoy.top/t/topic/pPiS 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录