fork download 
  1. /* 問題文 
  2.  
  3. 	有効グラフですべての頂点への道を持つ頂点があるかどうかを調べるプログラムを作成せよ
  4.     以下のソースコードを元にして作成すること
  5.     
  6.    ヒント
  7.    
  8.    　まず、グラフを強連結成分に分割する．この結果としてDAGが得られる．DAGの頂点のうち
  9.    　そこへ向かう辺が1本も無い頂点を考える．このような頂点が複数あれば、そのグラフに
  10.    　すべての頂点への道を持つ頂点は無い．一つだけあればそれが求める答である．この頂点
  11.    　に対応する元のグラフの頂点(その強連結成分に属する頂点)からは、すべての頂点への道
  12.    　がある．
  13. */
  14.  
  15.  
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18. #define N 6
  19.  
  20. struct edgecell {
  21.     int destination; /* 頂点番号 */
  22.     struct edgecell *next; /* 次の要素を指すポインタ */
  23. };
  24.  
  25. struct node {
  26.     struct edgecell *adjlist; 
  27.     int seq;
  28. };
  29.  
  30. struct node vertex[N+1];
  31. int counter = 0, sp = 0, stack[N+1];
  32. int scomponent[N+1][N+1] 
  33. int scomponent_index; 
  34.  
  35. void strongcomponent(void);
  36.  
  37. void insertNode(struct node *cell, int dest) {
  38.     struct edgecell *next = cell->adjlist;
  39.     if (next == NULL) {
  40. 	cell->adjlist = malloc(sizeof(struct edgecell));
  41. 	cell->adjlist->destination = dest;
  42. 	cell->adjlist->next = NULL;
  43.     } else {
  44. 	while (next->next != NULL) {
  45. 	    next = next->next;
  46. 	}
  47. 	next->next = malloc(sizeof(struct edgecell));
  48. 	next->next->destination = dest;
  49. 	next->next->next = NULL;
  50.     }
  51. }
  52.  
  53. int main(void) {
  54.     int i;
  55.     insertNode(&vertex[1], 2);
  56.     insertNode(&vertex[2], 1);
  57.     insertNode(&vertex[2], 6);
  58.     insertNode(&vertex[3], 1);
  59.     insertNode(&vertex[3], 4);
  60.     insertNode(&vertex[4], 2);
  61.     insertNode(&vertex[4], 5);
  62.     insertNode(&vertex[4], 6);
  63.     insertNode(&vertex[5], 3);
  64.  
  65. #ifdef NDEBUG
  66.     for (i = 1; i <= N; i++) {
  67. 	struct edgecell *next = vertex[i].adjlist;
  68. 	printf("%d: ", i);
  69.  
  70. 	/* リストの末尾の要素を探す */
  71. 	while (next != NULL) {
  72. 	    printf("%d ", next->destination);
  73. 	    next = next->next;
  74. 	}
  75. 	printf("\n");
  76.     }
  77.     printf("\n");
  78. #endif
  79.  
  80.     strongcomponent();
  81.  
  82.     for (i = 0; i < scomponent_index; i++) {
  83. 	int j = 0;
  84. 	while (scomponent[i][j] != 0) {
  85. 	    printf("%d,", scomponent[i][j]);
  86. 	    j++;
  87. 	}
  88. 	printf("\n");
  89.     }
  90. }
  91.  
  92. int visit(int v) {
  93.     int min, m, x;
  94.     counter++; 
  95.     vertex[v].seq = counter; 
  96.     min = counter; stack[++sp] = v;
  97.     struct edgecell *p = vertex[v].adjlist;
  98.     while (p != NULL) {
  99. 	if (vertex[p->destination].seq == 0)
  100. 	    m = visit(p->destination);
  101. 	else
  102. 	    m = vertex[p->destination].seq;
  103. 	if (m < min) min = m;
  104. 	p = p->next;
  105.     }
  106.     if (min == vertex[v].seq) {
  107. 	int i = 0;
  108. 	do {
  109. 	    x = stack[sp--];
  110. 	    scomponent[scomponent_index][i++] = x;
  111. 	    vertex[x].seq = N + 1;
  112. 	} while (x != v);
  113. 	scomponent_index++;
  114.     }
  115.     return min;
  116. }
  117.  
  118. void strongcomponent(void) {
  119.     int i;
  120.     for (i = 1; i <= N; i++)
  121. 	vertex[i].seq = 0;
  122.  
  123. 	/* すべての頂点を開始頂点として探索し始める */
  124.     for (i = 1; i <= N; i++)
  125. 	if (vertex[i].seq == 0)  /* vertex[i].seqが0ならば、訪問済みでない(非連結グラフ対策) */
  126. 	    visit(i);
  127. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.c:33:1: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘int’
 int scomponent_index; 
 ^
prog.c: In function ‘main’:
prog.c:82:21: error: ‘scomponent_index’ undeclared (first use in this function)
     for (i = 0; i < scomponent_index; i++) {
                     ^
prog.c:82:21: note: each undeclared identifier is reported only once for each function it appears in
prog.c:84:9: error: ‘scomponent’ undeclared (first use in this function)
  while (scomponent[i][j] != 0) {
         ^
prog.c: In function ‘visit’:
prog.c:110:6: error: ‘scomponent’ undeclared (first use in this function)
      scomponent[scomponent_index][i++] = x;
      ^
prog.c:110:17: error: ‘scomponent_index’ undeclared (first use in this function)
      scomponent[scomponent_index][i++] = x;
                 ^
prog.c: In function ‘main’:
prog.c:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
stdout 
Standard output is empty
https://ideone.com/arXA0w
language:
C (gcc 8.3)
created:
10 years 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!