#include <cstdio> #include <algorithm> #include <vector> #include <queue> const int MAXN = 200 * 1000; std::vector<int> G[MAXN + 10]; std::vector<int> nG[MAXN + 10]; bool outOfGame[MAXN + 1], vis[MAXN + 1]; int deg[MAXN + 1]; std::vector<int> bfs(int v) { std::vector<int> ans; std::queue<int> q; q.push(v); int x; vis[v] = true; while(!q.empty()) { x = q.front(), q.pop(); ans.push_back(x); for (std::size_t i = 0; i < nG[x].size(); ++i) { if (!vis[nG[x][i]]) { q.push(nG[x][i]); vis[nG[x][i]] = true; } } } std::sort(ans.begin(), ans.end()); return ans; } int main(void) { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); for (int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } std::queue<int> q; for (int i = 1; i <= n; ++i) if (deg[i] < d) q.push(i), outOfGame[i] = true; int v, tmp; while(!q.empty()) { v = q.front(); q.pop(); for (std::size_t i = 0; i < G[v].size(); ++i) { tmp = G[v][i]; deg[tmp]--; if (deg[tmp] < d && !outOfGame[tmp]) q.push(tmp), outOfGame[tmp] = true; } } for (int i = 1; i <= n; ++i) { if (!outOfGame[i]) { for (std::size_t j = 0; j < G[i].size(); ++j) if (!outOfGame[G[i][j]]) nG[i].push_back(G[i][j]), nG[G[i][j]].push_back(i); } } int ans = 0; std::vector<int> ansVec, tmpVec; for (int i = 1; i <= n; ++i) { if (!outOfGame[i] && !vis[i]) { tmpVec = bfs(i); if (ansVec.empty()) ansVec = tmpVec; else if (ansVec.size() < tmpVec.size()) ansVec = tmpVec; } } if (ansVec.empty()) { puts("NIE"); return 0; } printf("%d\n", ansVec.size()); for (std::size_t i = 0; i < ansVec.size(); ++i) printf("%d ", ansVec[i]); 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 84 85 86 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> const int MAXN = 200 * 1000; std::vector<int> G[MAXN + 10]; std::vector<int> nG[MAXN + 10]; bool outOfGame[MAXN + 1], vis[MAXN + 1]; int deg[MAXN + 1]; std::vector<int> bfs(int v) { std::vector<int> ans; std::queue<int> q; q.push(v); int x; vis[v] = true; while(!q.empty()) { x = q.front(), q.pop(); ans.push_back(x); for (std::size_t i = 0; i < nG[x].size(); ++i) { if (!vis[nG[x][i]]) { q.push(nG[x][i]); vis[nG[x][i]] = true; } } } std::sort(ans.begin(), ans.end()); return ans; } int main(void) { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); for (int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } std::queue<int> q; for (int i = 1; i <= n; ++i) if (deg[i] < d) q.push(i), outOfGame[i] = true; int v, tmp; while(!q.empty()) { v = q.front(); q.pop(); for (std::size_t i = 0; i < G[v].size(); ++i) { tmp = G[v][i]; deg[tmp]--; if (deg[tmp] < d && !outOfGame[tmp]) q.push(tmp), outOfGame[tmp] = true; } } for (int i = 1; i <= n; ++i) { if (!outOfGame[i]) { for (std::size_t j = 0; j < G[i].size(); ++j) if (!outOfGame[G[i][j]]) nG[i].push_back(G[i][j]), nG[G[i][j]].push_back(i); } } int ans = 0; std::vector<int> ansVec, tmpVec; for (int i = 1; i <= n; ++i) { if (!outOfGame[i] && !vis[i]) { tmpVec = bfs(i); if (ansVec.empty()) ansVec = tmpVec; else if (ansVec.size() < tmpVec.size()) ansVec = tmpVec; } } if (ansVec.empty()) { puts("NIE"); return 0; } printf("%d\n", ansVec.size()); for (std::size_t i = 0; i < ansVec.size(); ++i) printf("%d ", ansVec[i]); return 0; } |