fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include <list>
  4. #define M 1000000007 
  5. using namespace std;
  6. int cnt; 
  7.  
  8. class Graph
  9. {
  10.     int V;    
  11.     list<int> *adj;    
  12.     public:
  13.     void dfs(int ,bool *);
  14.     Graph(int );   
  15.     void addEdge(int , int );   
  16.  
  17. };
  18.  
  19. Graph::Graph(int V)
  20. {
  21.     this->V = V;
  22.     adj = new list<int>[V];
  23.  
  24. }
  25.  
  26. void Graph::addEdge(int v, int w)
  27. {
  28.     adj[v].push_back(w); 
  29. }
  30.  
  31. void Graph::dfs(int v,bool visited[])
  32. {
  33.      cnt++;
  34.  
  35.     visited[v] = true;
  36.  
  37.  
  38.  
  39.     list<int>::iterator i;
  40.     for(i = adj[v].begin(); i != adj[v].end(); ++i)
  41.         if(!visited[*i])
  42.             dfs(*i,visited);
  43. }
  44.  
  45.  
  46.  
  47.  
  48. int main()
  49. {
  50.  
  51.     int T,n,m,i,x,y,ans;
  52.     long long count[100005];
  53.     long long int prod;
  54.     scanf("%d",&T);
  55.     while(T--)
  56.     {
  57.         scanf("%d%d",&n,&m);
  58.         Graph g(n);
  59.         for(i=1;i<=m;i++)
  60.         {
  61.              scanf("%d%d",&x,&y);                  
  62.              g.addEdge(x-1, y-1);
  63.              g.addEdge(y-1, x-1);
  64.         }
  65.         bool *visited= new bool[n];
  66.         for(i = 0; i <n; i++)
  67.         visited[i] = false;
  68.         for(i=0;i<n;i++)
  69.         {
  70.         	cnt=0;  
  71.             if(!visited[i])            
  72.             g.dfs(i,visited);
  73.             count[i]=cnt;
  74.         }
  75.        prod=1,ans=0;
  76.        for(i=0;i<n;i++)
  77.        {
  78.  
  79.          if(count[i]!=0)
  80.          {
  81.              ans++;           
  82.              prod=((prod%M)*(count[i]%M))%M;
  83.          }
  84.        } 
  85.        printf("%d %lld\n",ans,prod);
  86.     }
  87.  
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 4136KB
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/IgkFpM
language:
C++ (gcc 8.3)
created:
10 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!