Advertisement
Guest User

Untitled

a guest
Jun 24th, 2019
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct stack{
  5. int value;
  6. struct stack* next;
  7. } Stack;
  8.  
  9. typedef struct graph{
  10. int color;
  11. Stack* Next;
  12. } Graph;
  13.  
  14. void push(Stack**stack, int value) {
  15. Stack* tmp = malloc(sizeof(Stack));
  16. tmp->value = value;
  17. tmp->next = *stack;
  18. *stack = tmp;
  19. }
  20.  
  21.  
  22. int freeStack(Stack* stack) {
  23. while (stack) {
  24. int value = (stack)->value;
  25. Stack* tmp = stack;
  26. stack = (stack)->next;
  27. free(tmp);
  28. return value;
  29. }
  30. }
  31.  
  32.  
  33. Graph* buildGraph(int n, int m) {
  34. Graph* graph = malloc(sizeof(Graph) * n);
  35. for (int i = 0; i < n; i++) {
  36. graph[i].color = 0;
  37. graph[i].Next = 0;
  38. }
  39. int a, b;
  40. for (int i = 0; i < m; i++) {
  41. if (scanf("%d%d", &a, &b) < 2) {
  42. for (int j = 0; j < n; j++) {
  43. freeStack(graph[j].Next);
  44. }
  45. free(graph);
  46. printf("bad number of lines");
  47. return 0;
  48. }
  49. if ((a < 1) || (a > n) || (b < 1) || (b > n)) {
  50. for (int i = 0; i < n; i++) {
  51. freeStack(graph[i].Next);
  52. }
  53. free(graph);
  54. printf("bad vertex");
  55. return NULL;
  56. } push(&graph[a - 1].Next, b - 1);
  57. }
  58. return graph;
  59. }
  60.  
  61. void dfs(Graph* graph, int vertex, Stack** sortedGraph, int* cycle) {
  62. graph[vertex].color = 1;
  63. Stack* tmp = graph[vertex].Next;
  64. while (tmp) {
  65. if (graph[tmp->value].color == 0) {
  66. dfs(graph, tmp->value, sortedGraph, cycle);
  67. }
  68. if (graph[tmp->value].color == 1) {
  69. *cycle = 1;
  70. }
  71. tmp = tmp->next;
  72. }
  73. graph[vertex].color = 2;
  74. push(sortedGraph, vertex);
  75. }
  76.  
  77.  
  78. Stack* topSort(Graph* graph, int n) {
  79. int cycle = 0;
  80. Stack* sortedGraph = NULL;
  81. for (int i = 0; i < n; i++) {
  82. if (graph[i].color == 0) {
  83. dfs(graph, i, &sortedGraph, &cycle);
  84. }
  85. if (cycle) {
  86. printf("impossible to sort");
  87. freeStack(sortedGraph);
  88. return NULL;
  89. }
  90. }
  91. return sortedGraph;
  92. }
  93.  
  94. int main() {
  95. int n, m;
  96. if (scanf("%d%d", &n, &m) != 2) {
  97. printf("bad number of lines\n");
  98. return 0;
  99. } else {
  100. if (( n > 1000)|| (n < 0)) {
  101. printf("bad number of vertices\n");
  102. return 0;
  103. } else {
  104. if ((m > n*(n - 1) / 2) || (m < 0)) {
  105. printf("bad number of edges\n");
  106. return 0;
  107. }
  108. }
  109. }
  110.  
  111. Graph* graph = buildGraph(n, m);
  112. if (!graph) {
  113. return 0;
  114. }
  115. Stack* sortedGraph = topSort(graph, n);
  116. if (sortedGraph) {
  117. while (sortedGraph) {
  118. int value = (sortedGraph)->value;
  119. Stack *tmp = sortedGraph;
  120. sortedGraph = (sortedGraph)->next;
  121. free(tmp);
  122. printf("%d ", value + 1);
  123. }
  124. }
  125.  
  126. for (int i = 0; i < n; i++) {
  127. freeStack(graph[i].Next);
  128. }
  129. free(graph);
  130.  
  131. return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement