时间限制: 1 Sec 内存限制: 128 MB 提交: 71 解决: 33 [提交] [状态] [命题人:admin]
题目描述
小花梨给出n个点，让k位同学对这n个点任意添加无向边，构成k张图。小花梨想知道对于每个点i，存在多少个点j（包括i本身），使得i和j在这k张图中都是连通的。
输入
第一行输入两个正整数n和k，分别表示点的个数和同学数。 接下来分成k部分进行输入，每部分输入格式相同。 每部分第一行输入一个整数ai，表示第i位同学连边的数目。 接下来ai行，每行两个正整数u,v，表示第i位同学将点u和点v之间进行连接。 可能会存在重边或者自环。(1≤n≤100000,1≤k≤10,1≤u,v≤n,0≤ai≤200000)
输出
输出n行，第i行输出在k张图中都和编号为i的点连通的点的数目(包括i本身)
复制样例数据
4 2 3 1 2 1 3 2 3 2 1 2 3 4样例输出
2 2 1 1
[提交][状态]
思路：用并查集进行染色，然后用map确定个数
算是头一回知道vector也能放在map里映射吧
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 100; int fa[maxn], n; vector<int> s[maxn]; map<vector<int>, int> p; void init() { for (int i = 1; i <= n; i++) fa[i] = i; } int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); } void Union(int x, int y) { int fx = Find(x), fy = Find(y); if (fx != fy) { if (fx < fy) fa[fy] = fx; else fa[fx] = fy; } } int main() { int k; scanf("%d%d", &n, &k); while (k--) { int m, u, v; scanf("%d", &m); init(); while (m--) { scanf("%d%d", &u, &v); Union(u, v); } for (int i = 1; i <= n; i++) { s[i].push_back(Find(i)); } } for (int i = 1; i <= n; i++) p[s[i]]++; for (int i = 1; i <= n; i++) { printf("%d\n", p[s[i]]); } return 0; }
