fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define N_VERTICES_NO_MIN	1
  4. #define N_VERTICES_NO_MAX	(100 + 10)
  5.  
  6. typedef enum
  7. {
  8. 	EDGE_NO_0,
  9. 	EDGE_YES_1
  10. }EdgeExists;
  11. typedef enum
  12. {
  13. 	PROCESSED_NO_0,
  14. 	PROCESSED_ING_1,
  15. 	PROCESSED_YES_2
  16. }_VertexProcessedState;
  17. typedef struct
  18. {
  19. 	_VertexProcessedState IsProcessed;
  20. }_VertexInfo;
  21.  
  22. EdgeExists Edges[N_VERTICES_NO_MAX][N_VERTICES_NO_MAX];
  23. int AdjacencyList[N_VERTICES_NO_MAX][N_VERTICES_NO_MAX];
  24. _VertexInfo VertexInfo[N_VERTICES_NO_MAX];
  25. int N_Vertex_No = 0;
  26. int Start_Vertex_Count = 0, Start_Vertices[N_VERTICES_NO_MAX];
  27. int Processed_Vertices[N_VERTICES_NO_MAX];
  28.  
  29. void DFS(int startVertex)
  30. {
  31. 	int i = 0;
  32.  
  33. 	VertexInfo[startVertex].IsProcessed = PROCESSED_ING_1;
  34.  
  35. 	for (i = 0; i < AdjacencyList[startVertex][N_VERTICES_NO_MAX - 1]; i++)
  36. 	{
  37. 		if (VertexInfo[AdjacencyList[startVertex][i]].IsProcessed == PROCESSED_NO_0)
  38. 		{
  39. 			DFS(AdjacencyList[startVertex][i]);
  40. 		}
  41. 	}
  42.  
  43. 	VertexInfo[startVertex].IsProcessed = PROCESSED_YES_2;
  44. 	Processed_Vertices[Processed_Vertices[N_VERTICES_NO_MAX - 1]++] = startVertex;
  45. }
  46. void resetVertexProcessedInfo()
  47. {
  48. 	int i = 0;
  49. 	for (i = 1; i <= N_Vertex_No; i++)
  50. 	{
  51. 		VertexInfo[i].IsProcessed = PROCESSED_NO_0;
  52. 	}
  53. }
  54. void resetEdgesAdjacencyList(int noOfVertex)
  55. {
  56. 	int i = 0, j = 0;
  57. 	for (i = 0; i <= noOfVertex; i++)
  58. 	{
  59. 		AdjacencyList[i][N_VERTICES_NO_MAX - 1] = 0;
  60. 		VertexInfo[i].IsProcessed = PROCESSED_NO_0;
  61.  
  62. 		for (j = 0; j <= noOfVertex; j++)
  63. 		{
  64. 			Edges[i][j] = EDGE_NO_0;
  65. 		}
  66. 	}
  67. }
  68. void initialize()
  69. {
  70. 	resetEdgesAdjacencyList(N_VERTICES_NO_MAX);
  71. }
  72. void resetTestCase(int noOfVertex)
  73. {
  74. 	resetEdgesAdjacencyList(noOfVertex);
  75. }
  76. void scanEdges()
  77. {
  78. 	int vertex_from = 0;
  79.  
  80. 	while (scanf("%d", &vertex_from) == 1 && vertex_from != 0)
  81. 	{
  82. 		int vertex_to = 0;
  83.  
  84. 		while (scanf("%d", &vertex_to) == 1 && vertex_to != 0)
  85. 		{
  86. 			Edges[vertex_from][vertex_to] = EDGE_YES_1;
  87. 			AdjacencyList[vertex_from][AdjacencyList[vertex_from][N_VERTICES_NO_MAX - 1]++] = vertex_to;
  88. 		}
  89. 	}
  90. }
  91. void scanStartVertices()
  92. {
  93. 	int start_Vertex_Index = 0;
  94.  
  95. 	scanf("%d", &Start_Vertex_Count);
  96.  
  97. 	for (start_Vertex_Index = 0; start_Vertex_Index < Start_Vertex_Count; start_Vertex_Index++)
  98. 	{
  99. 		scanf("%d", &Start_Vertices[start_Vertex_Index]);
  100. 	}
  101. }
  102. void scanInput()
  103. {
  104. 	scanEdges();
  105. 	scanStartVertices();
  106. }
  107. void processStartVertex(int startVertex)
  108. {
  109. 	int i = 0;
  110. 	for (i = 0; i < AdjacencyList[startVertex][N_VERTICES_NO_MAX - 1]; i++)
  111. 	{
  112. 		if (VertexInfo[AdjacencyList[startVertex][i]].IsProcessed == PROCESSED_NO_0)
  113. 		{
  114. 			DFS(AdjacencyList[startVertex][i]);
  115. 		}
  116. 	}
  117. }
  118. void printResult()
  119. {
  120. 	int i = 0;
  121. 	printf("%d", N_Vertex_No - Processed_Vertices[N_VERTICES_NO_MAX - 1]);
  122. 	for (i = 1; i <= N_Vertex_No; i++)
  123. 	{
  124. 		if (VertexInfo[i].IsProcessed != PROCESSED_YES_2)
  125. 		{
  126. 			printf(" %d", i);
  127. 		}
  128. 	}
  129. 	printf("\n");
  130. }
  131.  
  132. int main()
  133. {
  134. #ifdef __FREOPEN__
  135. 	freopen("280 - Vertex.in", "r", stdin);
  136. #endif
  137. 	initialize();
  138. 	while (scanf("%d", &N_Vertex_No) == 1 && N_Vertex_No != 0)
  139. 	{
  140. 		int startVertexIndex = 0;
  141.  
  142. 		scanInput();
  143.  
  144. 		for (startVertexIndex = 0; startVertexIndex < Start_Vertex_Count; startVertexIndex++)
  145. 		{
  146. 			Processed_Vertices[N_VERTICES_NO_MAX - 1] = 0;
  147. 			processStartVertex(Start_Vertices[startVertexIndex]);
  148. 			printResult();
  149. 			resetVertexProcessedInfo();
  150. 		}
  151.  
  152. 		resetTestCase(N_Vertex_No);
  153. 	}
  154. 	return 0;
  155. }
Success #stdin #stdout 0s 2260KB
comments (?)
stdin
copy 
3
2 3 0
3 1 2 0
0
3 1 2 3

8
2 3 4 8 0
3 1 6 0
4 3 5 7 0
5 2 3 6 8 0
6 1 3 4 5 0
7 1 3 5 6 0
8 2 3 4 5 0
0
8 1 2 3 4 5 6 7 8

4
1 2 4 0
2 3 0
3 1 2 4 0
4 1 2 0
0
4 1 2 3 4

1
0
1 1

9
1 6 8 0
2 1 4 6 9 0
3 2 4 5 8 9 0
4 5 7 0
5 1 3 4 8 9 0
6 2 3 4 5 7 9 0
7 1 2 3 4 0
8 1 2 3 4 6 9 0
9 1 2 5 7 0
0
9 1 2 3 4 5 6 7 8 9


0
stdout
copy 
3 1 2 3
0
0
8 1 2 3 4 5 6 7 8
0
0
0
0
0
0
0
0
0
0
0
1 1
0
0
0
0
0
0
0
0
0
https://ideone.com/gbgMwN
language:
C (gcc 8.3)
created:
8 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!