fork download
copy 
  1. #include <iostream>
  2. #define FIN "graf.in"
  3. #define FOUT "graf.out"
  4. #define SIZE 100
  5.  
  6. using namespace std;
  7.  
  8. int mat[ SIZE ][ SIZE ], succ[SIZE],
  9.                      prec[SIZE],
  10. nodes, start_node, nrc;
  11.  
  12. //                           1
  13. // succesorii nodului i ..sunt nodurile j pentru care exista drum de la i la j
  14. void Depth_First_Search1( int node ) {
  15.  
  16.     int k;
  17.  
  18.     succ[ node ] = nrc;
  19.  
  20.     for(k = 1; k <= nodes; ++k) {
  21.  
  22.         if(mat[ node ][ k ] == 1 && succ[k] == 0) Depth_First_Search1( k );
  23.     }
  24. }
  25.  
  26. void Depth_First_Search2(int node) {
  27.  
  28.      int k;
  29.  
  30.      prec[ node ] = nrc;
  31.  
  32.      for(k = 1; k <= nodes; ++k) {
  33.  
  34.          if(mat[ k ][ node ] && prec[ k ] == 0) {
  35.  
  36.             Depth_First_Search2( k );
  37.          }
  38.      }
  39.  
  40. }
  41.  
  42.  
  43. void read_graph() {
  44.  
  45.      int i, j;
  46.  
  47.      //freopen(FIN,"r",stdin);
  48.  
  49.      cin>>nodes;
  50.  
  51.      while( cin>>i>>j ) {
  52.  
  53.            mat[i][j] = 1;
  54.      }
  55.  
  56. }
  57.  
  58. int main(int argc, char const *argv[]) {
  59.  
  60.   read_graph();
  61.  
  62.   nrc = 1;
  63.  
  64.   for(int i = 1; i <= nodes; ++i) {
  65.  
  66.       if(succ[ i ] == 0) {
  67.  
  68.          succ[ i ] = nrc;
  69.  
  70.          //marcam succesorii
  71.          Depth_First_Search1( i );
  72.  
  73.          //marcam predecesorii
  74.          Depth_First_Search2( i );
  75.  
  76.          for(int j = 1; j <= nodes; ++j)
  77.  
  78.             if(succ[j]!=prec[j]) succ[j] = prec[j] = 0;
  79.  
  80.          nrc++;
  81.       }
  82.   }
  83.  
  84.  
  85.   for(int i = 1; i < nrc; ++i) {
  86.  
  87.       printf("Componenta %d: ", i);
  88.  
  89.       for(int j = 1; j <= nodes; ++j) {
  90.  
  91.         if(succ[ j ] == i) printf("%d ", j);
  92.       }
  93.  
  94.       cout<<"\n";
  95.   }
  96.  
  97. //1 2 3 4 5
  98. //1 1 1 1 1
  99. //1 1 1 0 0
  100.  
  101. //1 1 1 0 0
  102. //1 1 1 0 0
  103.  
  104.  
  105.   return 0;
  106. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
5
1 2
2 3
3 1
1 4
4 5
5 4
stdout
copy 
Componenta 1: 1 2 3 
Componenta 2: 4 5
https://ideone.com/UtIsbM
Decomposition of the graph into strongly connected components.
language:
C++14 (gcc 8.3)
created:
279 days 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!