“美登杯” C. 小花梨判连通 *

　　https://acm.ecnu.edu.cn/contest/173/problem/C/

题意：给定n个点和基于这n个点为基的k张无向图   输出每个点所在的联通块数量 （ 满足所有的图）

并查集并不好操作

可以 进行dfs染色  然后把染色情况加入到color  再进行映射  显然如果两个点的染色情况完全一样  那么就在同一点

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f

const int N=100000+5;

map<vector<int>,int>mp;
vector<int>color[N],edge[N];
int n,m,u,v,q,cnt,vis[N];

void dfs(int u)
{
    color[u].pb(cnt);vis[u]=1;
    for(int i=0;i<edge[u].size();i++)
    if(!vis[edge[u][i]])
    dfs(edge[u][i]);
}
int main()
{
    RII(n,m);
    rep(i,1,m)
    {
        RI(q);
        rep(i,1,n)edge[i].clear(),vis[i]=0;
        while(q--)
        {
            RII(u,v);
            edge[u].pb(v);
            edge[v].pb(u);
        }
        cnt=0;
        rep(i,1,n)
        if(!vis[i])dfs(i),++cnt;
    }

    rep(i,1,n)mp[color[i]]++;rep(i,1,n)
    cout<<mp[color[i]]<<endl;

    return 0;
}