#include <vector> #include <queue> #include <iostream> using namespace std; vector<int> best_component(const vector<vector<int>> &G, const vector<bool> &valid) { vector<int> visited(G.size(), 0); for (auto i = 1; i < G.size(); i++) if (!valid[i]) visited[i] = -1; int i = 1, k = 1, best = 0, best_k = 0; while (i < G.size()) { if (visited[i]) { i++; continue; } int num = 0; queue<int> Q; Q.push(i); while (!Q.empty()) { int v = Q.front(); Q.pop(); visited[v] = k; num++; for (auto w : G[v]) if (!visited[w]) Q.push(w); } if (num > best) { best = num; best_k = k; } k++; } vector<int> out; if (best_k > 0) { out.reserve(best); for (auto i = 0; i < G.size(); i++) if (visited[i] == best_k) out.push_back(i); } return out; } int main() { ios_base::sync_with_stdio(false); int n, m, d; int w, v; cin >> n >> m >> d; vector<vector<int>> G(n + 1, vector<int>()); vector<int> degs(n + 1, 0); vector<bool> valid(n + 1, false); queue<int> to_remove; for (auto i = 0; i < m; ++i) { cin >> w >> v; G[w].push_back(v); G[v].push_back(w); degs[w]++; degs[v]++; valid[w] = valid[v] = true; } for (auto i = 1; i <= n; ++i) { if (degs[i] < d) to_remove.push(i); } while (!to_remove.empty()) { v = to_remove.front(); to_remove.pop(); valid[v] = false; for (auto w : G[v]) { if (valid[w] && --degs[w] < d) to_remove.push(w); } } auto out = best_component(G, valid); if (out.empty()) cout << "NIE" << endl; else { cout << out.size() << endl; for (auto x : out) cout << x << " "; cout << endl; } return 0; }
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 | #include <vector> #include <queue> #include <iostream> using namespace std; vector<int> best_component(const vector<vector<int>> &G, const vector<bool> &valid) { vector<int> visited(G.size(), 0); for (auto i = 1; i < G.size(); i++) if (!valid[i]) visited[i] = -1; int i = 1, k = 1, best = 0, best_k = 0; while (i < G.size()) { if (visited[i]) { i++; continue; } int num = 0; queue<int> Q; Q.push(i); while (!Q.empty()) { int v = Q.front(); Q.pop(); visited[v] = k; num++; for (auto w : G[v]) if (!visited[w]) Q.push(w); } if (num > best) { best = num; best_k = k; } k++; } vector<int> out; if (best_k > 0) { out.reserve(best); for (auto i = 0; i < G.size(); i++) if (visited[i] == best_k) out.push_back(i); } return out; } int main() { ios_base::sync_with_stdio(false); int n, m, d; int w, v; cin >> n >> m >> d; vector<vector<int>> G(n + 1, vector<int>()); vector<int> degs(n + 1, 0); vector<bool> valid(n + 1, false); queue<int> to_remove; for (auto i = 0; i < m; ++i) { cin >> w >> v; G[w].push_back(v); G[v].push_back(w); degs[w]++; degs[v]++; valid[w] = valid[v] = true; } for (auto i = 1; i <= n; ++i) { if (degs[i] < d) to_remove.push(i); } while (!to_remove.empty()) { v = to_remove.front(); to_remove.pop(); valid[v] = false; for (auto w : G[v]) { if (valid[w] && --degs[w] < d) to_remove.push(w); } } auto out = best_component(G, valid); if (out.empty()) cout << "NIE" << endl; else { cout << out.size() << endl; for (auto x : out) cout << x << " "; cout << endl; } return 0; } |