#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, m, d, a, b; int deg[N]; bool done[N], vis[N]; vector<int> V[N]; queue<int> Q; vector<int> visitedNodes; void DFS(int w) { vis[w] = true; visitedNodes.push_back(w); for (int i = 0; i < V[w].size(); i++) { int u = V[w][i]; if (!vis[u] && !done[u]) { vis[u] = true; DFS(u); } } } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 1; i <= m; i++) { scanf("%d %d", &a, &b); V[a].push_back(b); V[b].push_back(a); deg[a]++; deg[b]++; } for (int i = 1; i <= n; i++) { if (deg[i] < d) { Q.push(i); done[i] = true; } } while (!Q.empty()) { int w = Q.front(); Q.pop(); for (int i = 0; i < V[w].size(); i++) { int u = V[w][i]; deg[u]--; if (done[u] == false && deg[u] < d) { done[u] = true; Q.push(u); } } } vector<int> bestResult; for (int i = 1; i <= n; i++) { if (!done[i] && !vis[i]) { visitedNodes.clear(); DFS(i); if (bestResult.size() < visitedNodes.size()) { bestResult = visitedNodes; } } } if (bestResult.size() < d) { printf("NIE\n"); } else { printf("%d\n", bestResult.size()); sort(bestResult.begin(), bestResult.end()); for (int i = 0; i < bestResult.size(); i++) { printf("%d ", bestResult[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 | #include <bits/stdc++.h> using namespace std; const int N = 200005; int n, m, d, a, b; int deg[N]; bool done[N], vis[N]; vector<int> V[N]; queue<int> Q; vector<int> visitedNodes; void DFS(int w) { vis[w] = true; visitedNodes.push_back(w); for (int i = 0; i < V[w].size(); i++) { int u = V[w][i]; if (!vis[u] && !done[u]) { vis[u] = true; DFS(u); } } } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 1; i <= m; i++) { scanf("%d %d", &a, &b); V[a].push_back(b); V[b].push_back(a); deg[a]++; deg[b]++; } for (int i = 1; i <= n; i++) { if (deg[i] < d) { Q.push(i); done[i] = true; } } while (!Q.empty()) { int w = Q.front(); Q.pop(); for (int i = 0; i < V[w].size(); i++) { int u = V[w][i]; deg[u]--; if (done[u] == false && deg[u] < d) { done[u] = true; Q.push(u); } } } vector<int> bestResult; for (int i = 1; i <= n; i++) { if (!done[i] && !vis[i]) { visitedNodes.clear(); DFS(i); if (bestResult.size() < visitedNodes.size()) { bestResult = visitedNodes; } } } if (bestResult.size() < d) { printf("NIE\n"); } else { printf("%d\n", bestResult.size()); sort(bestResult.begin(), bestResult.end()); for (int i = 0; i < bestResult.size(); i++) { printf("%d ", bestResult[i]); } } return 0; } |