#include <cstdio> #include <vector> #include <algorithm> int N,M,D; bool valid[200100]; bool visited[200100]; int cnt[200100]; std::vector<int> bad; std::vector<int> edges[200100]; void dfs(int v, std::vector<int> &nodes) { visited[v] = true; nodes.push_back(v); for (int i=0; i<edges[v].size(); ++i) { int next = edges[v][i]; if (valid[next] && !visited[next]) dfs(next, nodes); } } int main() { scanf("%d %d %d",&N,&M,&D); for (int i=1;i<=N;++i) { cnt[i]=0; valid[i]=true; visited[i]=false; } for (int i=0;i<M;++i) { int a,b; scanf("%d %d",&a,&b); cnt[a]++; cnt[b]++; edges[a].push_back(b); edges[b].push_back(a); } for (int i=1;i<=N;++i) { if (cnt[i]<D) { valid[i] = false; bad.push_back(i); } } while (!bad.empty()) { int node = *bad.rbegin(); bad.pop_back(); for (int i=0; i<edges[node].size(); ++i) { int next = edges[node][i]; cnt[next]--; if (valid[next] && cnt[next]<D) { valid[next] = false; bad.push_back(next); } } } std::vector<int> result; for (int i=1; i<=N;++i) { if (valid[i] && !visited[i]) { std::vector<int> component; dfs(i, component); if (component.size() > result.size()) result = component; } } if (result.size() > 0) { std::sort(result.begin(), result.end()); printf("%d\n",(int)result.size()); for (int i=0;i<result.size();++i) printf("%d ",result[i]); } 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 80 | #include <cstdio> #include <vector> #include <algorithm> int N,M,D; bool valid[200100]; bool visited[200100]; int cnt[200100]; std::vector<int> bad; std::vector<int> edges[200100]; void dfs(int v, std::vector<int> &nodes) { visited[v] = true; nodes.push_back(v); for (int i=0; i<edges[v].size(); ++i) { int next = edges[v][i]; if (valid[next] && !visited[next]) dfs(next, nodes); } } int main() { scanf("%d %d %d",&N,&M,&D); for (int i=1;i<=N;++i) { cnt[i]=0; valid[i]=true; visited[i]=false; } for (int i=0;i<M;++i) { int a,b; scanf("%d %d",&a,&b); cnt[a]++; cnt[b]++; edges[a].push_back(b); edges[b].push_back(a); } for (int i=1;i<=N;++i) { if (cnt[i]<D) { valid[i] = false; bad.push_back(i); } } while (!bad.empty()) { int node = *bad.rbegin(); bad.pop_back(); for (int i=0; i<edges[node].size(); ++i) { int next = edges[node][i]; cnt[next]--; if (valid[next] && cnt[next]<D) { valid[next] = false; bad.push_back(next); } } } std::vector<int> result; for (int i=1; i<=N;++i) { if (valid[i] && !visited[i]) { std::vector<int> component; dfs(i, component); if (component.size() > result.size()) result = component; } } if (result.size() > 0) { std::sort(result.begin(), result.end()); printf("%d\n",(int)result.size()); for (int i=0;i<result.size();++i) printf("%d ",result[i]); } else { printf("NIE\n"); } return 0; } |