fork(6) download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #define MAXV 1000
  5. using namespace std;
  6.  
  7. typedef vector <int> vi;
  8.  
  9. // Assuming vertices are labeled 0...V-1
  10. vi G[MAXV], Grev[MAXV];
  11. bool explored[MAXV];
  12. int leader[MAXV], finish[MAXV], order[MAXV], t = -1, parent = 0, V, E;
  13.  
  14. // running DFS on the reverse graph
  15. void dfs_reverse(int i) {
  16.     explored[i] = true;
  17.     for(vi::iterator it = Grev[i].begin(); it != Grev[i].end(); it++)
  18.         if(!explored[*it])
  19.             dfs_reverse(*it);
  20.     t++;
  21.     finish[i] = t;
  22. }
  23.  
  24. // running DFS on the actual graph
  25. void dfs(int i) {
  26.     explored[i] = true;
  27.     leader[i] = parent;
  28.     for(vi::iterator it = G[i].begin(); it != G[i].end(); it++)
  29.         if(!explored[*it])
  30.             dfs(*it);
  31. }
  32.  
  33. // check if u & v are in the same connected component
  34. bool stronglyConnected(int u, int v)    {
  35.     return leader[u] == leader[v];
  36. }
  37.  
  38. int main()  {
  39.     int i, u, v, countCC, Q;
  40.  
  41.     //freopen("input.txt", "r", stdin);
  42.  
  43.     scanf("%d %d", &V, &E); // Enter the number of vertices & edges
  44.     for(i=0; i<E; i++)  {   // Enter E edges : u -> v
  45.         scanf("%d %d", &u, &v);
  46.         G[u].push_back(v);  // Insert into the adjacency list of the graph
  47.         Grev[v].push_back(u);   // and the reverse graph
  48.     }
  49.  
  50.     printf("Original graph :\n");
  51.     for(i=0; i<V; i++)  {
  52.         if(!G[i].empty())   {
  53.             printf("%d : ", i);
  54.             for(vi::iterator it = G[i].begin(); it != G[i].end(); it++)
  55.                 printf("%d ", *it);
  56.             printf("\n");
  57.         }
  58.     }
  59.  
  60.     printf("Reverse graph :\n");
  61.     for(i=0; i<V; i++)  {
  62.         if(!Grev[i].empty())   {
  63.             printf("%d : ", i);
  64.             for(vi::iterator it = Grev[i].begin(); it != Grev[i].end(); it++)
  65.                 printf("%d ", *it);
  66.             printf("\n");
  67.         }
  68.     }
  69.  
  70.     // run dfs on the reverse graph to get reverse postorder
  71.     memset(explored, false, V*sizeof(bool));
  72.     for(i=0; i<V; i++)  {
  73.         if(!explored[i])
  74.             dfs_reverse(i);
  75.         order[finish[i]] = i;
  76.     }
  77.  
  78.     // run dfs on the actual graph in reverse postorder
  79.     memset(explored, false, V*sizeof(bool));
  80.     countCC = 0;
  81.     for(i=V-1; i>=0; i--)
  82.         if(!explored[order[i]]) {
  83.             parent = order[i];
  84.             dfs(order[i]);
  85.             countCC++;
  86.         }
  87.  
  88.     printf("No. of strongly connected components : %d\n", countCC);
  89.     scanf("%d", &Q); // Enter number of SCC queries
  90.     while(Q--)  {
  91.         scanf("%d %d", &u, &v);
  92.         stronglyConnected(u, v) ? printf("YES\n") : printf("NO\n");
  93.     }
  94.     return 0;
  95. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oPnraZ
language:
Text (text 6.10)
created:
9 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!