#include <algorithm> #include <iostream> #include <cstdio> #include <set> #include <unordered_set> #include <vector> using namespace std; typedef pair<int, int> pii; const int N_MAX = 2e5+10; int n, m, d; bool removed[N_MAX]; unordered_set<int> g[N_MAX]; set<pii> q; int component[N_MAX]; inline pii key(int v) { return {g[v].size(), v}; } int dfs(int v, int p) { int res = 1; component[v] = component[p]; for (auto w : g[v]) { if (!component[w]) { res += dfs(w, v); } } return res; } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); g[a].insert(b); g[b].insert(a); } for (int v = 1; v <= n; v++) { q.insert(key(v)); } while (!q.empty() && q.begin()->first < d) { int v = q.begin()->second; // cerr << q.begin()->first << ' ' << v << '\n'; removed[v] = true; q.erase(key(v)); for (auto w : g[v]) { if (removed[w]) continue; q.erase(key(w)); g[w].erase(v); q.insert(key(w)); } } // cerr << q.size() << '\n'; pii ans = {0, -1}; for (int v = 1; v <= n; v++) { if (removed[v] || component[v]) continue; component[v] = v; pii res = {dfs(v, v), v}; ans = max(ans, res); } // cerr << ans.first << ' ' << ans.second << '\n'; if (ans.first) { printf("%d\n", ans.first); for (int v = 1; v <= n; v++) { if (component[v] == ans.second) printf("%d ", v); } printf("\n"); } else { printf("NIE\n"); } 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 | #include <algorithm> #include <iostream> #include <cstdio> #include <set> #include <unordered_set> #include <vector> using namespace std; typedef pair<int, int> pii; const int N_MAX = 2e5+10; int n, m, d; bool removed[N_MAX]; unordered_set<int> g[N_MAX]; set<pii> q; int component[N_MAX]; inline pii key(int v) { return {g[v].size(), v}; } int dfs(int v, int p) { int res = 1; component[v] = component[p]; for (auto w : g[v]) { if (!component[w]) { res += dfs(w, v); } } return res; } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); g[a].insert(b); g[b].insert(a); } for (int v = 1; v <= n; v++) { q.insert(key(v)); } while (!q.empty() && q.begin()->first < d) { int v = q.begin()->second; // cerr << q.begin()->first << ' ' << v << '\n'; removed[v] = true; q.erase(key(v)); for (auto w : g[v]) { if (removed[w]) continue; q.erase(key(w)); g[w].erase(v); q.insert(key(w)); } } // cerr << q.size() << '\n'; pii ans = {0, -1}; for (int v = 1; v <= n; v++) { if (removed[v] || component[v]) continue; component[v] = v; pii res = {dfs(v, v), v}; ans = max(ans, res); } // cerr << ans.first << ' ' << ans.second << '\n'; if (ans.first) { printf("%d\n", ans.first); for (int v = 1; v <= n; v++) { if (component[v] == ans.second) printf("%d ", v); } printf("\n"); } else { printf("NIE\n"); } return 0; } |