#include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; vector<int> G[200005]; int deg[200005]; bool vst[200005]; vector<int> ans, V; void dfs(int s) { vst[s] = true; for (int i = 0; i < G[s].size(); i++) { int u = G[s][i]; if (vst[u] or deg[u] <= 0) continue; dfs(u); } V.push_back(s); } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin >> n >> m >> d; while(m--) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } //for (int i = 1; i <= n; i++) cout << i << " " << deg[i] << "\n"; queue<int> Q1, Q2; for (int i = 1; i <= n; i++) Q1.push(i); bool change = true; int cnt = n; while(change) { change = false; while(!Q1.empty()) { int v = Q1.front(); Q1.pop(); if (deg[v] < d) { for (int i = 0; i < G[v].size(); i++) deg[G[v][i]]--; deg[v] = 0; change = true; cnt--; } else Q2.push(v); } Q1 = Q2; while(!Q2.empty()) Q2.pop(); } //for (int i = 1; i <= n; i++) cout << i << " " << deg[i] << "\n"; if (cnt == 0) cout << "NIE\n"; else { for (int i = 1; i <= n; i++) { if (deg[i] > 0) { V.clear(); dfs(i); if (V.size() > ans.size()) ans = V; } } cout << ans.size() << "\n"; sort(ans.begin(), ans.end()); for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << "\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 80 81 82 83 | #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; vector<int> G[200005]; int deg[200005]; bool vst[200005]; vector<int> ans, V; void dfs(int s) { vst[s] = true; for (int i = 0; i < G[s].size(); i++) { int u = G[s][i]; if (vst[u] or deg[u] <= 0) continue; dfs(u); } V.push_back(s); } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin >> n >> m >> d; while(m--) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } //for (int i = 1; i <= n; i++) cout << i << " " << deg[i] << "\n"; queue<int> Q1, Q2; for (int i = 1; i <= n; i++) Q1.push(i); bool change = true; int cnt = n; while(change) { change = false; while(!Q1.empty()) { int v = Q1.front(); Q1.pop(); if (deg[v] < d) { for (int i = 0; i < G[v].size(); i++) deg[G[v][i]]--; deg[v] = 0; change = true; cnt--; } else Q2.push(v); } Q1 = Q2; while(!Q2.empty()) Q2.pop(); } //for (int i = 1; i <= n; i++) cout << i << " " << deg[i] << "\n"; if (cnt == 0) cout << "NIE\n"; else { for (int i = 1; i <= n; i++) { if (deg[i] > 0) { V.clear(); dfs(i); if (V.size() > ans.size()) ans = V; } } cout << ans.size() << "\n"; sort(ans.begin(), ans.end()); for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << "\n"; } return 0; } |