fork download 
  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;
  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 ] = start_node;//daca incep cu nodul 1 succ[1] = 1
  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 ] = start_node;
  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.   cout<<"Start Node = ";
  61.   cin>>start_node;
  62.  
  63.   read_graph();
  64.  
  65.  
  66.   succ[start_node] = start_node;
  67.   prec[ start_node ] = start_node;
  68.  
  69.   //apelam DFS pentru a marca succesorii nodului de start
  70.   Depth_First_Search1( start_node );
  71.   Depth_First_Search2( start_node );
  72.  
  73.   for(int i = 1; i <= nodes; ++i) printf("%d ", succ[i]);
  74.   printf("\n");
  75.   for(int i = 1; i <= nodes; ++i) printf("%d ", prec[i]);
  76.  
  77.   //apelam DFS pentru a marca predecesorii nodului de start
  78.   //Depth_First_Search2( start_node );
  79.  
  80.  
  81.   printf("\n%s: ", "Componenta Tare conexa careia ii apartine");
  82.  
  83.   for(int j = 1; j <= nodes; ++j) {
  84.  
  85.        if(succ[j] == prec[j] && succ[j] == start_node) {
  86.  
  87.         printf("%d ", j);
  88.        }
  89.   }
  90.  
  91.   return 0;
  92. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
1
5
1 2
2 3
3 1
1 4
4 5
5 4
stdout 
Start Node = 1 1 1 1 1 
1 1 1 0 0 
Componenta Tare conexa careia ii apartine: 1 2 3
https://ideone.com/kNc8bm
Given a node. output the strongly connected compontent.
language:
C++14 (gcc 8.3)
created:
250 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!