#include <bits/stdc++.h> using namespace std; vector<int>v[200007]; bool odw[200007]; int zbior[200007]; int licz[2000007]; queue<int>Q; int dfs(int a,int zb) { odw[a] = true; zbior[a] = zb; int ret = 1; for (int i = 0;i < v[a].size();i++) { if (!odw[v[a][i]]) ret += dfs(v[a][i],zb); } return ret; } int main() { int N,M,d; scanf("%d%d%d",&N,&M,&d); int a,b; for (int i = 0;i < M;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); licz[a]++; licz[b]++; } int il = 1; for (int i = 1;i <= N;i++) { if (licz[i] < d) { odw[i] = true; Q.push(i); } } while (!Q.empty()) { a = Q.front(); Q.pop(); licz[a] = 0; for (int i = 0;i < v[a].size();i++) { licz[v[a][i]]--; if (licz[v[a][i]] < d && !odw[v[a][i]]) { Q.push(v[a][i]); odw[v[a][i]] = true; } } } int maxlicz = 0; int ktory = 0; for (int i = 1;i <= N;i++) { if (!odw[i]) { a = dfs(i,il); if (a > maxlicz) { maxlicz = a; ktory = il; } il++; } } if (ktory == 0) { printf("NIE"); return 0; } printf("%d\n",maxlicz); for (int i = 1;i <= N;i++) { if (zbior[i] == ktory) printf("%d ",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 87 88 | #include <bits/stdc++.h> using namespace std; vector<int>v[200007]; bool odw[200007]; int zbior[200007]; int licz[2000007]; queue<int>Q; int dfs(int a,int zb) { odw[a] = true; zbior[a] = zb; int ret = 1; for (int i = 0;i < v[a].size();i++) { if (!odw[v[a][i]]) ret += dfs(v[a][i],zb); } return ret; } int main() { int N,M,d; scanf("%d%d%d",&N,&M,&d); int a,b; for (int i = 0;i < M;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); licz[a]++; licz[b]++; } int il = 1; for (int i = 1;i <= N;i++) { if (licz[i] < d) { odw[i] = true; Q.push(i); } } while (!Q.empty()) { a = Q.front(); Q.pop(); licz[a] = 0; for (int i = 0;i < v[a].size();i++) { licz[v[a][i]]--; if (licz[v[a][i]] < d && !odw[v[a][i]]) { Q.push(v[a][i]); odw[v[a][i]] = true; } } } int maxlicz = 0; int ktory = 0; for (int i = 1;i <= N;i++) { if (!odw[i]) { a = dfs(i,il); if (a > maxlicz) { maxlicz = a; ktory = il; } il++; } } if (ktory == 0) { printf("NIE"); return 0; } printf("%d\n",maxlicz); for (int i = 1;i <= N;i++) { if (zbior[i] == ktory) printf("%d ",i); } return 0; } |