fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <memory.h>
  4. #define FIN "bfs.in"
  5. #define FOUT "bfs.out"
  6. #define SIZE 100100
  7.  
  8. struct TNode {
  9. 	   int data;
  10. 	   struct TNode *next;
  11. };
  12.  
  13. typedef struct TNode Node;
  14.  
  15.  
  16. void addEdge(Node**list, int x, int y) {
  17.  
  18. 	Node *c = (Node*)malloc(sizeof(Node));
  19.  
  20. 	      c->data = y; 
  21. 	      c->next = list[x];
  22. 	      list[x] = c; 
  23. }
  24.  
  25. void bfs(Node **list, int nodes, int start) {
  26.  
  27.         int queue[ SIZE ],
  28.  
  29.             visited[ SIZE ],
  30.  
  31.             first = 0,
  32.  
  33.             last = 0,
  34.  
  35.             costs[nodes+1];
  36.  
  37.         memset(visited, 0, sizeof(visited));
  38.  
  39.         memset(costs, -1, sizeof(costs));
  40.  
  41.         costs[start] = 0;
  42.  
  43.         visited[ start ] = 1;
  44.  
  45.         queue[ first ] = start;
  46.  
  47.         while( first <= last ) {
  48.  
  49.               int node = queue[ first ];
  50.  
  51.               Node*curr = list[node];
  52.  
  53.               while(curr) {
  54.  
  55.                 if(visited[curr->data] == 0) {
  56.  
  57.                    queue[++last] = curr->data;
  58.  
  59.                    visited[curr->data] = 1;
  60.  
  61.                    costs[curr->data] = costs[node] + 1;
  62.  
  63.                 }     
  64.                 curr = curr->next;
  65.               }
  66.  
  67.               first++;                     
  68.  
  69.         }
  70.  
  71.         //freopen(FOUT, "w", stdout);
  72.  
  73.         for(int i = 1; i <= nodes; ++i) printf("%d ", costs[i]);
  74. }
  75.  
  76. int main(int argc, char const *argv[])
  77. {
  78.   	int nodes, edges, s, i, j; 
  79.   	Node *list[SIZE];
  80.  
  81.     //freopen(FIN, "r", stdin);
  82.  
  83.     scanf("%d %d %d" , &nodes, &edges, &s); 
  84.  
  85.     while(edges--) {
  86.  
  87.           scanf("%d %d" , &i, &j);
  88.  
  89.           addEdge(list, i,j);
  90.     }
  91.  
  92.     bfs(list, nodes, s);
  93. 	return 0;
  94. }
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
8 12 7
2 2
5 5
6 6
8 3
5 4
2 5
4 2
7 2
1 6
5 3
6 7
3 3
stdout
copy 
-1 1 3 3 2 -1 0 -1
https://ideone.com/f12bji
Breadth First Search with given Adjcency List. Computes minimum cost from a node. infoarena
language:
C (gcc 8.3)
created:
4 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!