fork(1) download
copy 
  1. #include <stdio.h>
  2. #define MAX_SIZE 100
  3. typedef struct{
  4.     int n,m;
  5.     int A[100][100];
  6. }Graph;
  7. void init_graph(Graph *G, int n){
  8.     G->n = n;
  9.     for(int u=1;u<=n;u++){
  10.         for(int v=1;v<=n;v++){
  11.             G->A[u][v] = 0;
  12.         }
  13.     }
  14.     G->m = 0;
  15. }
  16. void add_edge(Graph *G, int u, int v){
  17.     G->A[u][v]++;
  18.     G->A[v][u]++;
  19.     G->m++;
  20. }
  21. typedef struct{
  22. 	int data[MAX_SIZE];
  23. 	int front,rear;
  24. }Queue;
  25.  
  26. void makenullQueue(Queue *Q){
  27. 	Q->front = 0;
  28. 	Q->rear = -1;
  29. }
  30.  
  31. void enQueue(Queue *Q, int u){
  32. 	Q->rear++;
  33. 	Q->data[Q->rear] = u;
  34. }
  35.  
  36. int front(Queue *Q){
  37. 	return Q->data[Q->front];
  38. }
  39.  
  40. void deQueue(Queue *Q){
  41. 	Q->front++;
  42. }
  43.  
  44. int empty(Queue *Q){
  45. 	return Q->front > Q->rear;
  46. }
  47. int mark[100];
  48. void BFS(Graph *G, int x){
  49.     Queue Q;
  50.     makenullQueue(&Q);
  51.     enQueue(&Q,x);
  52.     while(!empty(&Q)){
  53.         int u = front(&Q);
  54.         deQueue(&Q);
  55.         if(mark[u]!=0) continue;
  56.         mark[u] = 1;
  57.         printf("%d\n", u);
  58.         for(int v=1;v<=G->n;v++){
  59.             if(G->A[u][v] > 0 && mark[v]==0){
  60.                 enQueue(&Q,v);
  61.             }
  62.         }
  63.     }
  64. }
  65. int main(){
  66.     Graph G;
  67. 	int n, m, u, v, e;
  68. 	scanf("%d%d", &n, &m);
  69. 	init_graph(&G, n);
  70.  
  71. 	for (e = 0; e < m; e++) {
  72. 		scanf("%d%d", &u, &v);
  73. 		add_edge(&G, u, v);
  74. 	}
  75. 	for(u=1;u<=G.n;u++){
  76. 		mark[u] = 0;
  77. 	}
  78. 	for(u=1;u<=G.n;u++){
  79. 		if(mark[u]==0)
  80. 		BFS(&G,u);
  81. 	}
  82.  
  83. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
13 16
1 4
1 2
1 12
2 4
3 7
4 6
4 7
5 6
5 8
5 9
6 7
6 13
8 9
10 11
10 12
11 12
stdout
copy 
1
2
4
12
6
7
10
11
5
13
3
8
9
https://ideone.com/xfE99B
language:
C (gcc 8.3)
created:
260 days ago
visibility:
public

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!