#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <queue> using namespace std; typedef long long ll; int main() { std::ios::sync_with_stdio(false); ll n, m, d; cin >> n >> m >> d; vector<set<ll> > adj(n); for (int i = 0; i < m; ++i) { ll a, b; cin >> a >> b; a--, b--; adj[a].insert(b); adj[b].insert(a); } queue<ll> delq; vector<int> deleted(adj.size()); for (int i = 0; i < adj.size(); ++i) if (adj[i].size() < d) delq.push(i); while (!delq.empty()) { auto e = delq.front(); delq.pop(); if (deleted[e]) continue; deleted[e] = 1; for (auto ee : adj[e]) { if (!deleted[ee]) { adj[ee].erase(e); if (adj[ee].size() < d) { delq.push(ee); } } } } /* for (int i = 0; i < n; ++i) { if (!deleted[i]) { cout << i << ": "; for (auto e : adj[i]) cout << e << " "; cout << endl; } } */ vector<int> color(n, -1); int currCol = 0; for (int i = 0; i < n; ++i) { if (!deleted[i] && color[i] == -1) { queue<ll> q; q.push(i); color[i] = currCol; while (!q.empty()) { auto idx = q.front(); color[i] = currCol; q.pop(); for (auto e : adj[idx]) { if (!deleted[e] && color[e] == -1) { color[e] = currCol; q.push(e); } } } } currCol++; } map<int, int> mm; for (auto e : color) if (e != -1) mm[e]++; int maxIdx = -1; for (auto e : mm) { if (maxIdx == -1 || e.second > mm[maxIdx]) maxIdx = e.first; } if (maxIdx == -1) { cout << "NIE" << endl; } else { cout << mm[maxIdx] << endl; for (int i = 0; i < color.size(); ++i) { if (color[i] == maxIdx) { cout << i+1 << " "; } } 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 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 105 106 107 108 109 110 | #include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <queue> using namespace std; typedef long long ll; int main() { std::ios::sync_with_stdio(false); ll n, m, d; cin >> n >> m >> d; vector<set<ll> > adj(n); for (int i = 0; i < m; ++i) { ll a, b; cin >> a >> b; a--, b--; adj[a].insert(b); adj[b].insert(a); } queue<ll> delq; vector<int> deleted(adj.size()); for (int i = 0; i < adj.size(); ++i) if (adj[i].size() < d) delq.push(i); while (!delq.empty()) { auto e = delq.front(); delq.pop(); if (deleted[e]) continue; deleted[e] = 1; for (auto ee : adj[e]) { if (!deleted[ee]) { adj[ee].erase(e); if (adj[ee].size() < d) { delq.push(ee); } } } } /* for (int i = 0; i < n; ++i) { if (!deleted[i]) { cout << i << ": "; for (auto e : adj[i]) cout << e << " "; cout << endl; } } */ vector<int> color(n, -1); int currCol = 0; for (int i = 0; i < n; ++i) { if (!deleted[i] && color[i] == -1) { queue<ll> q; q.push(i); color[i] = currCol; while (!q.empty()) { auto idx = q.front(); color[i] = currCol; q.pop(); for (auto e : adj[idx]) { if (!deleted[e] && color[e] == -1) { color[e] = currCol; q.push(e); } } } } currCol++; } map<int, int> mm; for (auto e : color) if (e != -1) mm[e]++; int maxIdx = -1; for (auto e : mm) { if (maxIdx == -1 || e.second > mm[maxIdx]) maxIdx = e.first; } if (maxIdx == -1) { cout << "NIE" << endl; } else { cout << mm[maxIdx] << endl; for (int i = 0; i < color.size(); ++i) { if (color[i] == maxIdx) { cout << i+1 << " "; } } cout << endl; } } |