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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <cstdint>
#include <vector>
#include <queue>

using std::vector;
using std::queue;

const int32_t kNoColor = 0;

class Node {
  public:
    vector<Node*> neighbours;
    int32_t neighbourCandidatesCount = 0;
    bool isCandidate = true;
    int32_t color = kNoColor;
};

//long node_id(Node *all_nodes, Node *node) {
//  return 1 + ((long)node - (long)all_nodes) / (long)sizeof(Node);
//}

int32_t main() {
    int32_t total_nodes,
            total_edges,
            minimum_connections;
    scanf("%d%d%d", &total_nodes, &total_edges, &minimum_connections);
    Node nodes[total_nodes];
    for (int32_t i = 0; i < total_edges; i++) {
        int32_t from, to;
        scanf("%d%d", &from, &to);
        from--; to--;
//        printf("edge: %d <-> %d\n", from, to);
        nodes[from].neighbours.push_back(&nodes[to]);
        nodes[to].neighbours.push_back(&nodes[from]);
    }
    for (int32_t i = 0; i < total_nodes; i++) {
        nodes[i].neighbourCandidatesCount = nodes[i].neighbours.size();
//         printf("%d ", nodes[i].neighbourCandidatesCount);
    }
//    printf(": initial neighbour count\n");
    // Find initial dropouts
    queue<Node*> bfs_queue;
    for (int32_t i = 0; i < total_nodes; i++) {
        if (nodes[i].neighbourCandidatesCount < minimum_connections) {
            bfs_queue.push(&nodes[i]);
//            printf("%ld ", node_id(nodes, &nodes[i]));
        }
    }
//    printf(": initial dropouts\n");
    // Recursively cut down graph
    while (!bfs_queue.empty()) {
        Node *node = bfs_queue.front();
        bfs_queue.pop();
        if (node->isCandidate == false) {
            continue;
        }
        node->isCandidate = false;
        for (int32_t i = 0; i < node->neighbours.size(); i++) {
            Node *neighbour = node->neighbours[i];
            neighbour->neighbourCandidatesCount--;
            if (neighbour->neighbourCandidatesCount < minimum_connections) {
                bfs_queue.push(neighbour);
            }
        }
    }
//    for (int32_t i = 0; i < total_nodes; i++) {
//        if (nodes[i].isCandidate) {
//            printf("%d ", i + 1);
//        }
//    }
//    printf(": candidates\n");
    // Color graph
    // bfs_queue is empty now
    int32_t current_color = kNoColor;
    for (int32_t j = 0; j < total_nodes; j++) {
        if (nodes[j].color == kNoColor && nodes[j].isCandidate) {
            current_color++;
            bfs_queue.push(&nodes[j]);
            while (!bfs_queue.empty()) {
                Node *node = bfs_queue.front();
                bfs_queue.pop();
                if (node->color != kNoColor) {
                    continue;
                }
                node->color = current_color;
                for (int32_t i = 0; i < node->neighbours.size(); i++) {
                    Node *neighbour = node->neighbours[i];
                    if (neighbour->isCandidate) {
                        bfs_queue.push(neighbour);
                    }
                }
            }
        }
    }
//    for (int32_t i = 0; i < total_nodes; i++) {
//        printf("%d ", nodes[i].color);
//    } printf(": colors\n");
    // Zero color counts
    int32_t total_colors = current_color + 1;
    int32_t color_counts[current_color + 1];
    for (int32_t i = 0; i < total_colors; i++) {
        color_counts[i] = 0;
    }
    // Count colors
    for (int32_t i = 0; i < total_nodes; i++) {
        color_counts[nodes[i].color]++;
    }
    // Find best color
    int32_t best_color = kNoColor;
    int32_t best_color_nodes_count = INT32_MIN;
    for (int32_t i = 1; i < total_colors; i++) {
        if (best_color_nodes_count < color_counts[i]) {
            best_color = i;
            best_color_nodes_count = color_counts[i];
        }
    }
    // Print result
    if (best_color == kNoColor) {
        printf("NIE\n");
    } else {
        printf("%d\n", best_color_nodes_count);
        for (int32_t i = 0; i < total_nodes; i++) {
            if (nodes[i].color == best_color) {
                printf("%d ", i + 1);
            }
        }
        printf("\n");
    }
    return 0;
}