fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <string.h>
  4. #define fin "strongly.in"
  5. #define STACK_MAX 100
  6. #define DIM 100
  7.  
  8. typedef struct Node {
  9.         int info;
  10.         struct Node *next;
  11. } Node;
  12.  
  13. int nodes,
  14.     edges,
  15.     comp;
  16. Node *L[DIM],
  17.      *L_Reverse[DIM],
  18.      *Result[DIM];
  19.  
  20. int explored[DIM];
  21.  
  22. #include <stdio.h>
  23. #define STACK_MAX 100
  24. #define FIN "scarface.in"
  25.  
  26. struct Stack {
  27.  
  28. 	int size;
  29. 	char data[ STACK_MAX ];
  30. };
  31.  
  32. typedef struct Stack Stack;
  33.  
  34. void Stack_Init(Stack *S) {
  35.  
  36.      S->size = 0;
  37. }
  38.  
  39. int Stack_Empty(Stack *S) {
  40.  
  41.      return S->size == 0;
  42. }
  43.  
  44. void Stack_Push(Stack *S, int val) {
  45.  
  46.      if( S->size < STACK_MAX ) {
  47.  
  48.          S->data[S->size++] = val;
  49.  
  50.      } else fprintf(stderr, "Err: Stack Full!\n");
  51.  
  52. }
  53.  
  54. void Stack_Pop(Stack *S) {
  55.  
  56.      if( S->size == 0 ) fprintf(stderr, "Error: Stack Empty!");
  57.  
  58.          else S->size--;
  59. }
  60.  
  61. int Stack_Top(Stack *S) {
  62.  
  63. 	if(S->size == 0) {
  64.  
  65.        fprintf(stderr, "Error: Stack Empty!");
  66.        return -1;
  67. 	}
  68.  
  69.     return S->data[ S->size - 1];
  70. }
  71.  
  72. Stack S;
  73.  
  74. void readGraph() {
  75.      int x, y;
  76.      //freopen(fin, "r", stdin);
  77.      scanf("%d %d", &nodes, &edges);
  78.      while(edges--) {
  79.        scanf("%d %d", &x, &y);
  80.        Node*c = (Node*)malloc(sizeof(Node));
  81.        c->info = y;
  82.        c->next = L[x];
  83.        L[x] = c;
  84.        Node*c2 = (Node*)malloc(sizeof(Node));
  85.        c2->info = x;
  86.        c2->next = L_Reverse[y];
  87.        L_Reverse[y] = c2;
  88.      }
  89. }
  90.  
  91. void dfs(int node) {
  92.  
  93.      explored[node] = 1;
  94.  
  95.      Stack_Push(&S, node);
  96.  
  97.      Node *c = L[node];
  98.  
  99.      while(c) {
  100.  
  101.        if(!explored[c->info]) {
  102.  
  103.           dfs(c->info);
  104.        }
  105.  
  106.        c = c->next;
  107.      }
  108. }
  109.  
  110. void dfs_r(int node) {
  111.  
  112.      explored[ node ] = 1;
  113.  
  114.      Node*head = (Node*)malloc(sizeof(Node));
  115.      head->info = node;
  116.      head->next = Result[comp];
  117.      Result[comp] = head;
  118.  
  119.      Node *c = L_Reverse[node];
  120.  
  121.      while(c) {
  122.  
  123.        if(!explored[c->info]) {
  124.  
  125.           dfs_r(c->info);
  126.        }
  127.  
  128.        c = c->next;
  129.      }
  130. }
  131.  
  132. void kosaraju() {
  133.  
  134.   Stack_Init(&S);
  135.  
  136.   for(int node = 1; node <= nodes; ++node) {
  137.  
  138.       if(!explored[node]) {
  139.  
  140.         dfs(node);
  141.       }
  142.   }
  143.  
  144.    memset(explored, 0, sizeof(explored));
  145.  
  146.    int vertex;
  147.  
  148.    comp = 0;
  149.  
  150.    while(!Stack_Empty(&S)) {
  151.  
  152.          vertex = Stack_Top(&S);
  153.  
  154.          Stack_Pop(&S);
  155.  
  156.          if(!explored[vertex]) {
  157.  
  158.             comp++;
  159.  
  160.             dfs_r(vertex);
  161.          }
  162.    }
  163.  
  164.    for(int i = 1; i <= comp; ++i) {
  165.  
  166.        printf("Component %d:", i);
  167.  
  168.        Node *k = Result[i];
  169.  
  170.        while( k ) {
  171.  
  172.          printf("%d ", k->info);
  173.  
  174.          k = k -> next;
  175.        }
  176.  
  177.        printf("\n");
  178.  
  179.    }
  180. }
  181.  
  182. int main(int argc, char const *argv[]) {
  183.  
  184.   readGraph();
  185.  
  186.   kosaraju();
  187.  
  188.   return 0;
  189. }
  190.  
Success #stdin #stdout 0s 5436KB
comments (?)
stdin
copy 
5 6
1 2
1 4
2 3
3 1
4 5
5 4
stdout
copy 
Component 1:1 2 3 
Component 2:4 5
https://ideone.com/AhiTUU
Kosaraju's Algorithm
language:
C (gcc 8.3)
created:
2 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!