Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <string.h>
- #include <limits.h>
- #include <malloc.h>
- #include <stdlib.h>
- int *nodes, *num, n, m;
- typedef struct stack {
- int value;
- stack *next;
- }stack;
- typedef struct list {
- int value;
- list *next;
- }list;
- typedef struct masterList {
- masterList *next;
- masterList *prev;
- list *node;
- }masterList;
- masterList *Nodes = NULL;
- void push(stack **head, int data) {
- stack *p = (stack*)(malloc(sizeof(stack)));
- p->value = data;
- p->next = *head;
- *head = p;
- }
- void pushM(masterList **head, int data) {
- masterList *p, *t;
- p = *head;
- t = (masterList*)malloc(sizeof(masterList));
- t->node = (list*)malloc(sizeof(list));
- t->node->value = data;
- if (*head) {
- t->next = p->next;
- p->next = t;
- t->prev = p;
- t->next->prev = t;
- (*head)->next->node->next = NULL;
- }
- else {
- t->next = t;
- t->prev = t;
- (*head) = t;
- (*head)->node->next = NULL;
- }
- }
- void push0(list **head, int data) {
- list *p = (list*)malloc(sizeof(list)), *t;
- p->value = data;
- p->next = (*head)->next;
- (*head)->next = p;
- }
- list* searchMasterR(masterList *head, int n) {
- while (head->node->value != n) head = head->next;
- return(head->node);
- }
- list* searchMasterL(masterList *head, int n) {
- while (head->node->value != n) head = head->prev;
- return(head->node);
- }
- int search(list *head, int n) {
- head = head->next;
- while (head) {
- if (head->value == n) return 1;
- head = head->next;
- }
- return 0;
- }
- int pop(stack **head) {
- int value;
- stack *p = (stack*)(malloc(sizeof(stack)));
- p = (*head);
- *head = (*head)->next;
- value = p->value;
- free(p);
- return(value);
- }
- void dfs(int N, int count) {
- stack *head = NULL;
- list *t;
- int i, node;
- push(&head, N);
- while (head) {
- node = pop(&head);
- if (nodes[node] != 2) {
- nodes[node] = 2;
- num[node] = count + 1;
- if (N >= n / 2) t = searchMasterR(Nodes, node);
- else t = searchMasterL(Nodes, node);
- for (i = n - 1; i >= 0; i--) {
- if (nodes[i] != 2 && search(t, i)) {
- push(&head, i);
- nodes[i] = 1;
- }
- }
- }
- }
- } //обход в глубину
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int i, j, count, t1, t2;
- stack *head = NULL;
- list *t;
- count = 0;
- scanf("%d %d", &n, &m);
- num = (int*)malloc(n * sizeof(int));
- nodes = (int*)malloc(n * sizeof(int));
- pushM(&Nodes, n - 1);
- for (i = 0; i< n - 1; i++) pushM(&Nodes, i);
- while (scanf("%d", &t1) != EOF) {
- scanf("%d", &t2);
- t = searchMasterR(Nodes, --t1);
- push0(&t, --t2);
- t = searchMasterR(Nodes, t2);
- push0(&t, t1);
- }
- for (i = n - 1; i >= 0; i--) {
- if (nodes[i] != 2) {
- dfs(i, count);
- count++;
- }
- }
- printf("%d\n", count);
- for (i = 0; i < n; i++) printf("%d ", num[i]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement