fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #define FIN "topsort.in"
  4. #define DIM 100
  5.  
  6. typedef struct Node {
  7.      int info;
  8.      struct Node *next;
  9. } Node;
  10.  
  11. Node *ListAdj[ DIM ];
  12. Node *solutions;
  13. int explored[DIM];
  14. int nodes, edges;
  15.  
  16. void readListAdjcency() {
  17.  
  18.      int x, y;
  19.      Node *c;
  20.  
  21.      //freopen(FIN, "r", stdin);
  22.  
  23.      scanf("%d %d", &nodes, &edges);
  24.  
  25.      while(edges--){
  26.        scanf("%d %d", &x, &y);
  27.        Node *c = (Node*)malloc(sizeof(Node));
  28.        c->info = y;
  29.        c->next = ListAdj[x];
  30.        ListAdj[x] = c;
  31.      }
  32. }
  33.  
  34. void dfs(int node) {
  35.  
  36.      explored[node] = 1;
  37.  
  38.      Node *c = ListAdj[node];
  39.  
  40.      while(c!=NULL) {
  41.  
  42.        if(!explored[c->info]) {
  43.  
  44.          dfs(c->info);
  45.  
  46.        }
  47.  
  48.        c = c->next;
  49.      }
  50.  
  51.      Node*c2 = (Node*)malloc(sizeof(Node));
  52.      c2->info = node;
  53.      c2->next = solutions;
  54.      solutions = c2;
  55. }
  56.  
  57. void topsort() {
  58.  
  59.      for(int i = 1; i <= nodes; ++i) {
  60.        if(!explored[i]) {
  61.          dfs(i);
  62.        }
  63.      }
  64.  
  65.      Node *c = solutions;
  66.      while(c) {
  67.        printf("%d ", c->info);
  68.        c = c->next;
  69.      }
  70. }
  71.  
  72. int main(int argc, char const *argv[]) {
  73.  
  74.   readListAdjcency();
  75.   topsort();
  76.   return 0;
  77. }
  78.  
Success #stdin #stdout 0s 5436KB
comments (?)
stdin
copy 
8 9
1 2
1 3
3 4
3 5
4 6
4 7
4 8
5 9
stdout
copy 
1 2 3 4 6 7 8 5 9
https://ideone.com/o3aDYK
Topological Sorting
language:
C (gcc 8.3)
created:
1 year 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!