1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Tnode {
        int id;
        struct _Tnode * next;
} Tnode;

void removeEdge(Tnode *tab, int id, int to) {
        Tnode *t;

        tab[id].id--;

        t = tab[id].next;
        while (t->id != to) t = t->next;
        t->id = tab[id].next->id;
        t = tab[id].next;
        tab[id].next = t->next;
        free(t);
}

int main() {

        Tnode *tab, *t;
        int n,m,d,i,a,b,rm, *s;

        scanf("%d%d%d", &n, &m, &d);
        tab = malloc((n+1)*sizeof(*tab));
        for (i=0; i<=n; ++i) { tab[i].id = 0; tab[i].next = NULL; }

        for (i=0; i<m; ++i) {

                scanf("%d%d", &a, &b);

                t = malloc(sizeof(*t));
                t->id = b;
                t->next = tab[a].next;
                tab[a].id ++;
                tab[a].next = t;

                t = malloc(sizeof(*t));
                t->id = a;
                t->next = tab[b].next;
                tab[b].id ++;
                tab[b].next = t;
        }

        rm = 1;
        while (rm) {
                rm = 0;
                for (i=1; i<=n; ++i) {
                        if (tab[i].id && tab[i].id < d) { // REMOVE
                                tab[i].id = 0;
                                rm = 1;
                                while (NULL != (t = tab[i].next)) {
                                        tab[i].next = t->next;
                                        removeEdge(tab, t->id, i);
                                        free(t);
                                }
                        }
                }
        }

        for (i=1; i<=n; ++i)
                tab[i].id = (tab[i].id > 0) ? 0 : -1;

        for (i=1; i<=n; ++i) {
                if (tab[i].id == 0) tab[i].id = i;
                t = tab[i].next;
                while (t != NULL) {
                        tab[t->id].id = tab[i].id;
                        t = t->next;
                }
        }

        s = malloc((n+1)*sizeof(*s));
        bzero(s, (n+1)*sizeof(*s));
        a = b = 0;
        for (i=1; i<=n; ++i) {
                if (tab[i].id > 0 && ++s[tab[i].id] > a) {
                        a = s[tab[i].id];
                        b = tab[i].id;
                }
        }
        free(s);

        if (b == 0) {
                printf("NIE\n");
                free(tab);
                return 0;
        }

        rm = 0;
        for (i=1; i<=n; ++i)
                if (tab[i].id == b) rm++;
        printf("%d\n", rm);

        rm = 0;
        for (i=1; i<=n; ++i) {
                if (tab[i].id == b ) {
                        if (rm) printf(" ");
                        rm = 1;
                        printf("%d", i);
                }
        }
        printf("\n");
        free(tab);

        return 0;
}