#include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; #define PB push_back int m, n, d; const int N = 200005; int wyn, ileJuz; queue<int> kol; vector<int> sas[N]; int ileSas[N]; bool odw[N]; bool usuniete[N]; vector<int> aktV; vector<int> wynW; void dfs(int a) { aktV.PB(a); for (int i=0; i<sas[a].size(); i++) { if (!odw[sas[a][i]] && !usuniete[sas[a][i]]) { ileJuz++; odw[sas[a][i]] = true; dfs(sas[a][i]); } } } int main() { scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d",&a, &b); sas[a].PB(b); sas[b].PB(a); ileSas[a]++; ileSas[b]++; } for (int i=1; i<=n; i++) { if (ileSas[i] <d) { kol.push(i); usuniete[i] = true; } } while(!kol.empty()) { int a = kol.front(); kol.pop(); for (int i=0; i<sas[a].size(); i++) { if(!usuniete[sas[a][i]]) { ileSas[sas[a][i]]--; if (ileSas[sas[a][i]] < d) { usuniete[sas[a][i]] = true; kol.push(sas[a][i]); } } } } for (int i=1; i<=n; i++) { aktV.clear(); if (!usuniete[i]&&!odw[i]) { ileJuz = 1; odw[i] = true; dfs(i); } if(ileJuz > wyn) { wynW.clear(); for (int j=0; j<aktV.size(); j++) { wynW.PB(aktV[j]); } wyn = ileJuz; } } if (wyn > d) { printf("%d\n", wyn); sort(wynW.begin(), wynW.end()); for (int i=0; i<wynW.size(); i++) { printf("%d ", wynW[i]); } } else { printf("NIE\n"); } }
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 89 90 91 92 | #include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; #define PB push_back int m, n, d; const int N = 200005; int wyn, ileJuz; queue<int> kol; vector<int> sas[N]; int ileSas[N]; bool odw[N]; bool usuniete[N]; vector<int> aktV; vector<int> wynW; void dfs(int a) { aktV.PB(a); for (int i=0; i<sas[a].size(); i++) { if (!odw[sas[a][i]] && !usuniete[sas[a][i]]) { ileJuz++; odw[sas[a][i]] = true; dfs(sas[a][i]); } } } int main() { scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d",&a, &b); sas[a].PB(b); sas[b].PB(a); ileSas[a]++; ileSas[b]++; } for (int i=1; i<=n; i++) { if (ileSas[i] <d) { kol.push(i); usuniete[i] = true; } } while(!kol.empty()) { int a = kol.front(); kol.pop(); for (int i=0; i<sas[a].size(); i++) { if(!usuniete[sas[a][i]]) { ileSas[sas[a][i]]--; if (ileSas[sas[a][i]] < d) { usuniete[sas[a][i]] = true; kol.push(sas[a][i]); } } } } for (int i=1; i<=n; i++) { aktV.clear(); if (!usuniete[i]&&!odw[i]) { ileJuz = 1; odw[i] = true; dfs(i); } if(ileJuz > wyn) { wynW.clear(); for (int j=0; j<aktV.size(); j++) { wynW.PB(aktV[j]); } wyn = ileJuz; } } if (wyn > d) { printf("%d\n", wyn); sort(wynW.begin(), wynW.end()); for (int i=0; i<wynW.size(); i++) { printf("%d ", wynW[i]); } } else { printf("NIE\n"); } } |