#include <bits/stdc++.h> using namespace std; const int MAXN = 200000; int n, m, d, a, b, label; vector <int> G[MAXN + 5]; int deg[MAXN + 5]; bool bad[MAXN + 5]; int vis[MAXN + 5]; queue <int> Q; vector <int> res[MAXN + 5]; void dfs(int v); int main() { 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]++; } for(int i = 1; i <= n; ++i) Q.push(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(!bad[u] && deg[u] < d) { bad[u] = true; for(int i = 0; i < G[u].size(); ++i) { deg[G[u][i]]--; if(!bad[G[u][i]]) { Q.push(G[u][i]); } } } } for(int i = 1; i <= n; ++i) { if(!vis[i] && !bad[i]) { label = i; dfs(i); } } for(int i = 1; i <= n; ++i) { res[vis[i]].push_back(i); } int best = 0, best_pos = -1; for(int i = 1; i <= n; ++i) { if(res[i].size() > best) { best = res[i].size(); best_pos = i; } } if(best_pos == -1) { printf("NIE\n"); } else { printf("%d\n", best); sort(res[best_pos].begin(), res[best_pos].end()); for(int i = 0; i < res[best_pos].size(); ++i) { printf("%d ", res[best_pos][i]); } printf("\n"); } return 0; } void dfs(int v) { vis[v] = label; for(int i = 0; i < G[v].size(); ++i) { if(!vis[G[v][i]] && !bad[G[v][i]]) dfs(G[v][i]); } }
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 | #include <bits/stdc++.h> using namespace std; const int MAXN = 200000; int n, m, d, a, b, label; vector <int> G[MAXN + 5]; int deg[MAXN + 5]; bool bad[MAXN + 5]; int vis[MAXN + 5]; queue <int> Q; vector <int> res[MAXN + 5]; void dfs(int v); int main() { 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]++; } for(int i = 1; i <= n; ++i) Q.push(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(!bad[u] && deg[u] < d) { bad[u] = true; for(int i = 0; i < G[u].size(); ++i) { deg[G[u][i]]--; if(!bad[G[u][i]]) { Q.push(G[u][i]); } } } } for(int i = 1; i <= n; ++i) { if(!vis[i] && !bad[i]) { label = i; dfs(i); } } for(int i = 1; i <= n; ++i) { res[vis[i]].push_back(i); } int best = 0, best_pos = -1; for(int i = 1; i <= n; ++i) { if(res[i].size() > best) { best = res[i].size(); best_pos = i; } } if(best_pos == -1) { printf("NIE\n"); } else { printf("%d\n", best); sort(res[best_pos].begin(), res[best_pos].end()); for(int i = 0; i < res[best_pos].size(); ++i) { printf("%d ", res[best_pos][i]); } printf("\n"); } return 0; } void dfs(int v) { vis[v] = label; for(int i = 0; i < G[v].size(); ++i) { if(!vis[G[v][i]] && !bad[G[v][i]]) dfs(G[v][i]); } } |