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 | #include <algorithm>
#include <cstdint>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
int main()
{
std::uint_fast32_t n, m, d;
std::cin >> n >> m >> d;
std::vector<std::vector<decltype(n)>> edges(n);
for (decltype(m) i = 0; i < m; ++i)
{
decltype(n) city_1, city_2;
std::cin >> city_1 >> city_2;
--city_1;
--city_2;
edges[city_1].push_back(city_2);
edges[city_2].push_back(city_1);
}
for (auto& vertices : edges)
std::sort(vertices.begin(), vertices.end());
for (decltype(n) i = 0; i < n; ++i)
{
if (edges[i].size() < d)
{
std::stack<decltype(n)> stack;
stack.push(i);
while (!stack.empty())
{
auto top = stack.top();
stack.pop();
for (auto other_city : edges[top])
{
auto it = std::lower_bound(edges[other_city].begin(), edges[other_city].end(), top);
edges[other_city].erase(it);
if (edges[other_city].size() < d)
stack.push(other_city);
}
edges[top].clear();
}
}
}
const decltype(n) UNVISITED = n, PENDING = n + 1;
std::vector<decltype(n)> group_indexes(n, UNVISITED);
decltype(n) best_group_index = UNVISITED;
decltype(n) best_group_size = 1;
for (decltype(n) i = 0; i < n; ++i)
{
if (group_indexes[i] == UNVISITED)
{
decltype(n) group_size = 0;
std::stack<decltype(n)> stack;
stack.push(i);
while (!stack.empty())
{
auto top = stack.top();
stack.pop();
group_indexes[top] = i;
++group_size;
for (auto other_city : edges[top])
{
if (group_indexes[other_city] == UNVISITED)
{
stack.push(other_city);
group_indexes[other_city] = PENDING;
}
}
}
if (group_size > best_group_size)
{
best_group_size = group_size;
best_group_index = i;
}
}
}
if (best_group_index < n)
{
std::cout << best_group_size << std::endl;
std::cout << (best_group_index + 1);
for (decltype(n) i = best_group_index + 1; i < n; ++i)
{
if (group_indexes[i] == best_group_index)
std::cout << ' ' << (i + 1);
}
std::cout << std::endl;
}
else
std::cout << "NIE";
}
|