Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. enum Colour {
  5. WHITE, //0 ни разу НЕ ЗАХОДИЛИ
  6. GREY, //1 ЗАШЛИ , но обрабатываем следущие
  7. BLACK, //2 НИКУДА не ведет
  8. };
  9. typedef struct listNode {
  10. int from;
  11. int to;
  12. struct listNode * Next;
  13. } list;
  14.  
  15.  
  16. void matrix_create(list *mas, int rib_count , int top_count) // создание нового узла
  17. {
  18. int Start; //начало и конец ребра (S)-->(F)
  19. int Finish;
  20. for (int i = 0; i < rib_count; i++)
  21. {
  22. if (scanf("%d %d", &Start, &Finish) != 2) {
  23. printf("bad number of lines\n");
  24. exit(0);
  25. }
  26. if ((Start <= 0) || (Start > top_count) || (Finish <= 0) || (Finish > top_count)) {
  27. printf("bad vertex\n");
  28. exit(0);
  29. }
  30. mas[i].from = Start;
  31. mas[i].to = Finish;
  32. }
  33. }
  34.  
  35. void dfs(list *mas, char *WGB, int i, short int *out_put, int* p ,int rib_count)
  36. {
  37. int j;
  38. if (WGB[i - 1] == BLACK) {
  39. return;
  40. }
  41. //list *tmp = *List;
  42.  
  43. WGB[i - 1] = GREY;
  44. for (int z = 0; z< rib_count; z++)
  45. {
  46. if ((mas[j].from) == i)
  47. {
  48. if (WGB[(mas[j].to) - 1] == GREY)
  49. {
  50. printf("impossible to sort");
  51. exit(0);
  52. }
  53. if (WGB[(mas[j].to) - 1] == WHITE)
  54. {
  55. int l = mas[j].to;
  56. dfs(mas, WGB, l, out_put, p,mas,rib_count );//здесь вместо tmp->to нужно использовать рассматриваемае значение ранее
  57. }
  58. }
  59. j++;
  60. }
  61.  
  62. WGB[i - 1] = BLACK;
  63. out_put[(*p)++] = i;
  64. int k = *p - 1;
  65.  
  66. }
  67. int proverka(int top_count, int rib_count)
  68. {
  69. if (top_count > 1000 || top_count < 0)
  70. {
  71. printf("bad number of vertices");
  72. return 0;
  73. }
  74.  
  75. if (rib_count > top_count*(top_count + 1) / 2 || rib_count < 0)
  76. {
  77. printf("bad number of edges");
  78. return 0;
  79. }
  80. return 0;
  81. }
  82.  
  83. int main() {
  84.  
  85.  
  86.  
  87. list *head = malloc(sizeof(list));
  88.  
  89. int i, p = 0;
  90. int rib_count;
  91. int top_count;
  92. if (scanf("%d %d", &top_count, &rib_count) != 2) {
  93. printf("bad number of lines\n");
  94. return 0;
  95. }
  96. int *mas1 = (int*)malloc(sizeof(int));
  97. list *mas = malloc(sizeof(list));
  98. proverka(top_count, rib_count);
  99. short int *out_put = malloc(top_count * sizeof(int));
  100. char *WGB = (char*)calloc(top_count, sizeof(char));
  101.  
  102. matrix_create(head, rib_count, top_count);
  103.  
  104. for (i = 1; i <= top_count; i++) {
  105. dfs(mas, WGB, i, out_put, &p,rib_count);
  106. }
  107. for (i = 0; i < top_count; i++)
  108. {
  109. printf("%d\n", out_put[top_count - 1 - i]);
  110. }
  111. free(out_put);
  112. free(WGB);
  113. return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement