#include <iostream> #include <vector> using namespace std; int n, m, d, b; bool c[200000]; vector<int> w, v[200000]; int main() { ios_base::sync_with_stdio(0); cin >> n >> m >> d; for (int i = 0, x, y; i < m; ++i) { cin >> x >> y; v[x - 1].push_back(y - 1); v[y - 1].push_back(x - 1); } bool stop = false; while (!stop) { stop = true; for (int i = 0; i < n; ++i) { int num = v[i].size(); if (num != 0 && num < d) { stop = false; for (int j = 0; j < num; ++j) { int ver = v[i][j]; int f = 0, l = v[ver].size(); int mid = (f + l) / 2; while (v[ver][mid] != i) { if (v[ver][mid] < i) f = mid + 1; else l = mid - 1; mid = (f + l) / 2; } v[ver].erase(v[ver].begin() + mid); } v[i].clear(); } } } for (int i = 0; i < n; i++) { if (c[i] == false) { c[i] = true; vector<int> s; s.push_back(i); for (int it = 0; it < s.size(); ++it) { int top = s[it]; int num = v[top].size(); for (int j = 0; j < num; ++j) { if (!c[v[top][j]]) { c[v[top][j]] = true; s.push_back(v[top][j]); } } } if (s.size() > b) { b = s.size(); w.swap(s); } } } if (b <= 1) cout << "NIE" << endl; else { cout << b << endl; for (int i : w) cout << i + 1 << ' '; } 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 | #include <iostream> #include <vector> using namespace std; int n, m, d, b; bool c[200000]; vector<int> w, v[200000]; int main() { ios_base::sync_with_stdio(0); cin >> n >> m >> d; for (int i = 0, x, y; i < m; ++i) { cin >> x >> y; v[x - 1].push_back(y - 1); v[y - 1].push_back(x - 1); } bool stop = false; while (!stop) { stop = true; for (int i = 0; i < n; ++i) { int num = v[i].size(); if (num != 0 && num < d) { stop = false; for (int j = 0; j < num; ++j) { int ver = v[i][j]; int f = 0, l = v[ver].size(); int mid = (f + l) / 2; while (v[ver][mid] != i) { if (v[ver][mid] < i) f = mid + 1; else l = mid - 1; mid = (f + l) / 2; } v[ver].erase(v[ver].begin() + mid); } v[i].clear(); } } } for (int i = 0; i < n; i++) { if (c[i] == false) { c[i] = true; vector<int> s; s.push_back(i); for (int it = 0; it < s.size(); ++it) { int top = s[it]; int num = v[top].size(); for (int j = 0; j < num; ++j) { if (!c[v[top][j]]) { c[v[top][j]] = true; s.push_back(v[top][j]); } } } if (s.size() > b) { b = s.size(); w.swap(s); } } } if (b <= 1) cout << "NIE" << endl; else { cout << b << endl; for (int i : w) cout << i + 1 << ' '; } return 0; } |