#include <algorithm> #include <cstdio> #include <vector> #include <queue> #include <cassert> using namespace std; constexpr int MAXN = 200010; int N, D; bool removed[MAXN]; vector<int> neighbours[MAXN]; int deg[MAXN]; queue<int> throwem_out; vector<int> result; bool visited[MAXN]; // could also use removed instead void read_data() { int m; scanf("%d%d%d", &N, &m, &D); for (int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); --a; --b; neighbours[a].push_back(b); neighbours[b].push_back(a); ++deg[a]; ++deg[b]; } } void remove_infidels() { for (int i = 0; i < N; ++i) { if (deg[i] < D) { throwem_out.push(i); // printf("pushed %d\n", i); } } while (!throwem_out.empty()) { int curr = throwem_out.front(); throwem_out.pop(); if (removed[curr]) { continue; } removed[curr] = true; for (auto nei : neighbours[curr]) { // printf("%d -> %d (%d)\n", curr, nei, removed[nei]); if (removed[nei]) { continue; } --deg[nei]; if (deg[nei] < D) { throwem_out.push(nei); // printf("pushed %d\n", nei); } } } } void find_component_rec(int node) { if (visited[node]) { return; } visited[node] = true; result.push_back(node); for (int nei : neighbours[node]) { if (!removed[nei] && !visited[nei]) { find_component_rec(nei); } } } void find_component() { vector<int> best; for (int i = 0; i < N; ++i) { if (!removed[i] && !visited[i]) { find_component_rec(i); if (result.size() > best.size()) { best = std::move(result); assert(result.empty()); } result.clear(); } } if (best.empty()) { printf("NIE\n"); return; } sort(best.begin(), best.end()); printf("%d\n", best.size()); for (int node : best) { printf("%d ", node + 1); } printf("\n"); } int main() { read_data(); remove_infidels(); find_component(); }
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 | #include <algorithm> #include <cstdio> #include <vector> #include <queue> #include <cassert> using namespace std; constexpr int MAXN = 200010; int N, D; bool removed[MAXN]; vector<int> neighbours[MAXN]; int deg[MAXN]; queue<int> throwem_out; vector<int> result; bool visited[MAXN]; // could also use removed instead void read_data() { int m; scanf("%d%d%d", &N, &m, &D); for (int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); --a; --b; neighbours[a].push_back(b); neighbours[b].push_back(a); ++deg[a]; ++deg[b]; } } void remove_infidels() { for (int i = 0; i < N; ++i) { if (deg[i] < D) { throwem_out.push(i); // printf("pushed %d\n", i); } } while (!throwem_out.empty()) { int curr = throwem_out.front(); throwem_out.pop(); if (removed[curr]) { continue; } removed[curr] = true; for (auto nei : neighbours[curr]) { // printf("%d -> %d (%d)\n", curr, nei, removed[nei]); if (removed[nei]) { continue; } --deg[nei]; if (deg[nei] < D) { throwem_out.push(nei); // printf("pushed %d\n", nei); } } } } void find_component_rec(int node) { if (visited[node]) { return; } visited[node] = true; result.push_back(node); for (int nei : neighbours[node]) { if (!removed[nei] && !visited[nei]) { find_component_rec(nei); } } } void find_component() { vector<int> best; for (int i = 0; i < N; ++i) { if (!removed[i] && !visited[i]) { find_component_rec(i); if (result.size() > best.size()) { best = std::move(result); assert(result.empty()); } result.clear(); } } if (best.empty()) { printf("NIE\n"); return; } sort(best.begin(), best.end()); printf("%d\n", best.size()); for (int node : best) { printf("%d ", node + 1); } printf("\n"); } int main() { read_data(); remove_infidels(); find_component(); } |