#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; vector<vector<int>> graph(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a; --b; graph[a].push_back(b); graph[b].push_back(a); } vector<int> deg(n); for (int i = 0; i < n; ++i) deg[i] = graph[i].size(); vector<bool> solution(n, true); queue<int> to_remove; for (int i = 0; i < n; ++i) if (deg[i] < d) to_remove.push(i); while (!to_remove.empty()) { int u = to_remove.front(); to_remove.pop(); solution[u] = false; for (int v : graph[u]) if (solution[v]) { deg[v]--; if (deg[v] == d - 1) to_remove.push(v); } } vector<int> best; for (int i = 0; i < n; ++i) if (solution[i]) { vector<int> q; q.push_back(i); solution[i] = false; for (int j = 0; j < q.size(); ++j) { for (int v : graph[q[j]]) if (solution[v]) { q.push_back(v); solution[v] = false; } } if (q.size() > best.size()) best = q; } if (best.empty()) { cout << "NIE" << endl; } else { sort(best.begin(), best.end()); cout << best.size() << endl; for (int i = 0; i < best.size(); ++i) { if (i > 0) cout << " "; cout << 1 + best[i]; } cout << endl; } }
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 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; vector<vector<int>> graph(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a; --b; graph[a].push_back(b); graph[b].push_back(a); } vector<int> deg(n); for (int i = 0; i < n; ++i) deg[i] = graph[i].size(); vector<bool> solution(n, true); queue<int> to_remove; for (int i = 0; i < n; ++i) if (deg[i] < d) to_remove.push(i); while (!to_remove.empty()) { int u = to_remove.front(); to_remove.pop(); solution[u] = false; for (int v : graph[u]) if (solution[v]) { deg[v]--; if (deg[v] == d - 1) to_remove.push(v); } } vector<int> best; for (int i = 0; i < n; ++i) if (solution[i]) { vector<int> q; q.push_back(i); solution[i] = false; for (int j = 0; j < q.size(); ++j) { for (int v : graph[q[j]]) if (solution[v]) { q.push_back(v); solution[v] = false; } } if (q.size() > best.size()) best = q; } if (best.empty()) { cout << "NIE" << endl; } else { sort(best.begin(), best.end()); cout << best.size() << endl; for (int i = 0; i < best.size(); ++i) { if (i > 0) cout << " "; cout << 1 + best[i]; } cout << endl; } } |