Advertisement
Guest User

dfs

a guest
May 21st, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.79 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <string.h>
  4. #include <limits.h>
  5. #include <malloc.h>
  6. #include <stdlib.h>
  7.  
  8. int *nodes, *num, n, m;
  9.  
  10. typedef struct stack {
  11.     int value;
  12.     stack *next;
  13. }stack;
  14.  
  15. typedef struct list {
  16.     int value;
  17.     list *next;
  18. }list;
  19.  
  20. typedef struct masterList {
  21.     masterList *next;
  22.     masterList *prev;
  23.     list *node;
  24. }masterList;
  25.  
  26. masterList *Nodes = NULL;
  27.  
  28. void push(stack **head, int data) {
  29.     stack *p = (stack*)(malloc(sizeof(stack)));
  30.     p->value = data;
  31.     p->next = *head;
  32.     *head = p;
  33. }
  34.  
  35. void pushM(masterList **head, int data) {
  36.     masterList *p, *t;
  37.     p = *head;
  38.     t = (masterList*)malloc(sizeof(masterList));
  39.     t->node = (list*)malloc(sizeof(list));
  40.     t->node->value = data;
  41.     if (*head) {
  42.         t->next = p->next;
  43.         p->next = t;
  44.         t->prev = p;
  45.         t->next->prev = t;
  46.         (*head)->next->node->next = NULL;
  47.     }
  48.     else {
  49.         t->next = t;
  50.         t->prev = t;
  51.         (*head) = t;
  52.         (*head)->node->next = NULL;
  53.     }
  54. }
  55.  
  56. void push0(list **head, int data) {
  57.     list *p = (list*)malloc(sizeof(list)), *t;
  58.     p->value = data;
  59.     p->next = (*head)->next;
  60.     (*head)->next = p;
  61. }
  62.  
  63. list* searchMasterR(masterList *head, int n) {
  64.     while (head->node->value != n) head = head->next;
  65.     return(head->node);
  66. }
  67.  
  68. list* searchMasterL(masterList *head, int n) {
  69.     while (head->node->value != n) head = head->prev;
  70.     return(head->node);
  71. }
  72.  
  73. int search(list *head, int n) {
  74.     head = head->next;
  75.     while (head) {
  76.         if (head->value == n) return 1;
  77.         head = head->next;
  78.     }
  79.     return 0;
  80. }
  81.  
  82. int pop(stack **head) {
  83.     int value;
  84.     stack *p = (stack*)(malloc(sizeof(stack)));
  85.     p = (*head);
  86.     *head = (*head)->next;
  87.     value = p->value;
  88.     free(p);
  89.     return(value);
  90. }
  91.  
  92. void dfs(int N, int count) {
  93.     stack *head = NULL;
  94.     list *t;
  95.     int i, node;
  96.     push(&head, N);
  97.     while (head) {
  98.         node = pop(&head);
  99.         if (nodes[node] != 2) {
  100.             nodes[node] = 2;
  101.             num[node] = count + 1;
  102.             if (N >= n / 2) t = searchMasterR(Nodes, node);
  103.             else t = searchMasterL(Nodes, node);
  104.             for (i = n - 1; i >= 0; i--) {
  105.                 if (nodes[i] != 2 && search(t, i)) {
  106.                     push(&head, i);
  107.                     nodes[i] = 1;
  108.                 }
  109.             }
  110.         }
  111.     }
  112. } //обход в глубину
  113.  
  114. int main() {
  115.     freopen("input.txt", "r", stdin);
  116.     freopen("output.txt", "w", stdout);
  117.     int i, j, count, t1, t2;
  118.     stack *head = NULL;
  119.     list *t;
  120.     count = 0;
  121.     scanf("%d %d", &n, &m);
  122.     num = (int*)malloc(n * sizeof(int));
  123.     nodes = (int*)malloc(n * sizeof(int));
  124.     pushM(&Nodes, n - 1);
  125.     for (i = 0; i< n - 1; i++) pushM(&Nodes, i);
  126.     while (scanf("%d", &t1) != EOF) {
  127.         scanf("%d", &t2);
  128.         t = searchMasterR(Nodes, --t1);
  129.         push0(&t, --t2);
  130.         t = searchMasterR(Nodes, t2);
  131.         push0(&t, t1);
  132.     }
  133.     for (i = n - 1; i >= 0; i--) {
  134.         if (nodes[i] != 2) {
  135.             dfs(i, count);
  136.             count++;
  137.         }
  138.     }
  139.     printf("%d\n", count);
  140.     for (i = 0; i < n; i++) printf("%d ", num[i]);
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement