题目描述 小花梨给出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本身)
input 4 2 3 1 2 1 3 2 3 2 1 2 3 4 output 2 2 1 1 分析： 第一种方法：并查集 根据题意，如果n个点在这k个图里面是连通的，那么他们的祖先都是一样的，什么意思呢，就是那样例来说： 我们定义并查集的数组为f数组,初始化数组
f12341234在第一个同学连完线之后得到数组是
f12341114重新初始化数组后 在第二个同学连完线之后得到数组是
f12341133那么，如果我们将这n个点的祖先每次都存下来，那么就会发现下面这个
12341->11->11->34->3这样就会发现1号与2号是在在这2个子图中是连通的，因为每一次其祖先结点都是相同的，那么得到的祖先序列也是相同的，这里就是通过求祖先序列相同的个数来求得答案，当然你需要用到 map<vector ,int> 下面就AC的代码
#include <iostream> #include <algorithm> #include <string> #include <map> #include <cstring> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <set> #include <stack> using namespace std; typedef long long ll; const int N = 1e5+100; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const int MOD=1e9+7; #define rep(i,a,b) for(int i=a;i<=b;i++) #define Abs(x) ((x)>=0?(x):-(x)) vector<int> ve[N]; map<vector<int> ,int > ma; int f[N]; int findf(int v){ return f[v]==v ? v:f[v]=findf(f[v]); } void Merge(int x1,int x2){ int t1=findf(x1); int t2=findf(x2); if(t1!=t2){ if(t1<t2) f[t2]=t1; else f[t1]=t2; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE int n,m,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) f[i]=i; while(k--){ scanf("%d",&m); while(m--){int u,v; scanf("%d%d",&u,&v); Merge(u,v);//归并祖先 } for(int i=1;i<=n;i++){ ve[i].push_back(findf(i));//添加当前节点的祖先是谁 } for(int i=1;i<=n;i++) f[i]=i; } for(int i=1;i<=n;i++){ ma[ve[i]]++;//查找当前点的祖先序列有没有相似的 } for(int i=1;i<=n;i++) printf("%d\n",ma[ve[i]]); return 0; }当然这一道题目还可以用dfs搜索的方法去做，怎么去做呢？ 拿样例来说 3 1 2 1 3 2 3 可以把1 2 3的颜色都设置为1，4的颜色设置为2 2 1 2 3 4 可以把1 2 的颜色设置为1，3 4 的颜色设置为2 所心情况就是这样 点 k1 k2 1 1 1 2 1 1 3 1 2 4 2 2 点1和点2相同表示它们都有两个点相连，点3和点4各1个
#include <iostream> #include <algorithm> #include <string> #include <map> #include <cstring> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <set> #include <stack> using namespace std; typedef long long ll; const int N = 1e5+10; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const int MOD=1e9+7; #define rep(i,a,b) for(int i=a;i<=b;i++) #define Abs(x) ((x)>=0?(x):-(x)) vector<int>color[N],e[N]; map<vector<int>,int>num; int cnt; bool vis[N]; void dfs(int x){ vis[x]=1; color[x].push_back(cnt); for(int i=0;i<e[x].size();i++) if(!vis[e[x][i]]) dfs(e[x][i]); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE int n,k,m; scanf("%d%d",&n,&k); while(k--){int u,v; scanf("%d",&m); while(m--){ scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } cnt=0; for(int i=1;i<=n;i++) if(!vis[i]) cnt++,dfs(i); rep(i,1,n) e[i].clear(),vis[i]=false; } for(int i=1;i<=n;i++){ num[color[i]]++; } rep(i,1,n) printf("%d\n",num[color[i]]); return 0; }其实这两种方法的本质都是去找一个序列，然后将相同的序列加起来，这样得到的就是答案
