2019上海市高校大学生程序设计邀请赛（华东理工） C 小花梨判连通 并查集+map

本文主要是介绍2019上海市高校大学生程序设计邀请赛（华东理工） C 小花梨判连通 并查集+map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题 C: 小花梨判连通

时间限制: 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;
}

 

这篇关于2019上海市高校大学生程序设计邀请赛（华东理工） C 小花梨判连通 并查集+map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---