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
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

enum class Color {
    White,
    Gray,
    Black,
};

struct CityInfo {
    Color color;
    int connections;
    CityInfo() : color(Color::White), connections() {}
};

int main() {
    std::ios_base::sync_with_stdio(false);
    int n, m, d;
    std::cin >> n >> m >> d;
    std::vector<std::vector<int>> graph;
    graph.resize(n);
    int b, e;
    std::vector<CityInfo> cities;
    cities.resize(n);
    for (int i = 0; i < m; ++i) {
        std::cin >> b >> e;
        --b, --e;
        graph[b].push_back(e);
        graph[e].push_back(b);
        ++cities[b].connections;
        ++cities[e].connections;
    }
    std::vector<int> bfsVector;
    bfsVector.reserve(n);
    for (int i = 0; i < n; ++i) {
        if (cities[i].connections < d) {
            cities[i].color = Color::Gray;
            bfsVector.push_back(i);
        }
    }
    while (!bfsVector.empty()) {
        int city = bfsVector.back();
        bfsVector.pop_back();
        cities[city].color = Color::Black;
        for (auto neighbour : graph[city]) {
            if (cities[neighbour].color == Color::White && --cities[neighbour].connections < d) {
                cities[neighbour].color = Color::Gray;
                bfsVector.push_back(neighbour);
            }
        }
    }
    std::vector<std::vector<int>> connectedComponents;
    for (int i = 0; i < n; ++i) {
        if (cities[i].color == Color::White) {
            cities[i].color = Color::Gray;
            std::vector<int> componentBfs;
            componentBfs.push_back(i);
            connectedComponents.emplace_back();
            while (!componentBfs.empty()) {
                int elem = componentBfs.back();
                componentBfs.pop_back();
                connectedComponents.back().push_back(elem);
                for (auto neighbour : graph[elem]) {
                    if (cities[neighbour].color == Color::White) {
                        cities[neighbour].color = Color::Gray;
                        componentBfs.push_back(neighbour);
                    }
                }
            }
        }
    }
    if (connectedComponents.empty()) {
        std::cout << "NIE";
        return 0;
    }
    std::vector<int> *largestComponent = &connectedComponents.front();
    for (auto &component : connectedComponents) {
        if (largestComponent->size() < component.size()) {
            largestComponent = &component;
        }
    }
    std::cout << largestComponent->size() << '\n';
    std::sort(largestComponent->begin(), largestComponent->end());
    for (auto city : *largestComponent) {
        std::cout << city + 1 << ' ';
    }
}