problem : Teacher’s Dilemma
#include <iostream>
#include<vector>
using namespace std;
struct dsu
{
vector<int> par;
vector<long long> sz;
void init ( int n )
{
par.resize(n);
sz.resize(n);
for(int i=0;i<n;i++)
{par[i]=i;}
for(int i=0;i<n;i++)
{sz[i]=1;}
}
int get(int x)
{
if(x==par[x])
return x;
return par[x]=get(par[x]);
}
void unite(int x,int y)
{ int spx= get(x);
int spy = get(y);
if(spx!=spy)
{par[spx]=spy;
sz[spy]+=sz[spx];
sz[spx]=0;}
}
long long leader(int n)
{
long long ans=1;
for(int i=0;i<n;i++)
{if(sz[i]>0)
{ans*=(sz[i]% (1000000000+7));}
cout<<ans<<" ";
}
return ans;
}
} G;
int main() {
int n,m;
cin >> n>>m;
G.init(n);
for(int i =0;i<m;i++)
{
int x,y;
cin>>x>>y;
G.unite(x-1,y-1);
}
long long ans= G.leader(n);
cout<<"*"<<endl;
ans=ans%(1000000000+7);
cout<<ans<<endl;
return 0;
}