fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. ll mod=10e9+7;
  6. int find(int a[],int x)
  7. {
  8. 	if(x!=a[x])
  9. 	return find(a,a[x]);
  10. 	else
  11. 	return a[x];
  12. }
  13. void union_(int x,int y, int a[])
  14. {
  15. 	int x1=find(a,x);
  16. 	int y1=find(a,y);
  17. 	a[x1]=y1;
  18. }
  19. int main() {
  20. 	int t;
  21. 	cin>>t;
  22. 	while(t--)
  23. 	{
  24.               int n,m;
  25.               cin>>n>>m;
  26.               int a[n+1];
  27.               for(int i=0;i<=n;i++)
  28.               a[i]=i;
  29.               int u,v;
  30.               ll s=0,ans=1;
  31.               for(int i=0;i<m;i++)
  32.               {
  33.               	cin>>u>>v;
  34.               	union_(u,v,a);
  35.  
  36.  
  37.               }
  38.               ll hash[n+1];
  39.               memset(hash,0,sizeof(hash));
  40.               for(int i=1;i<=n;i++)
  41.               {
  42.               	hash[find(a,i)]++;
  43.               }
  44.               for(int i=1;i<=n;i++)
  45.               if(hash[i])
  46.               ans=(ans%mod)*(hash[i]%mod)%mod,s++;
  47.  
  48.  
  49.               cout<<s<<" "<<ans<<endl;
  50. 		}
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
3
4 2
1 2
2 3
5 3
1 2
2 3
1 3
6 3
1 2
3 4
5 6
stdout
copy 
2 3
3 3
3 8
https://ideone.com/gDZvZc
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!