#include<iostream> #include <vector> #include <algorithm> using namespace std; const long long int VV=200*1000+1; vector<int> tab[VV]; int deg[VV], repr[VV]; bool czy[VV], odw[VV]; int d, v, e, maxx, nr, bierz; int lsas(int ii) {return (tab[ii].size());} int isas(int ii, int iii) {return (tab[ii][iii]);} void wyrzuc(int kk) { int ii; czy[kk] = false; for (ii = 0; ii < lsas(kk); ii++) { deg[isas(kk,ii)]--; if ( (deg[isas(kk, ii)] < d) && czy[isas(kk, ii)] ) wyrzuc(isas(kk, ii)); } return; } void odwiedz(int kk, int reprez) { int ii; if (odw[kk] == false) { odw[kk] = true; repr[kk] = reprez; bierz++; for (ii = 0; ii < lsas(kk); ii++) if (czy[isas(kk, ii)]) odwiedz(isas(kk, ii), reprez); } } int i, j, k; int main() { ios_base::sync_with_stdio(0); cin >> v >> e >> d; for (i = 0; i < e; i++) { cin >> j >> k; tab[j].push_back(k); tab[k].push_back(j); } for (i = 1; i < v + 1; i++) { czy[i] = true; deg[i] = lsas(i); repr[i] = i; odw[i] = false; } for (i = 1; i < v + 1; i++) if ( (deg[i] < d) && czy[i] ) wyrzuc(i); maxx = 0; nr = -1; for (i = 1; i < v + 1; i++) if ((odw[i] == false) && czy[i] ) { bierz = 0; odwiedz(i, i); if (maxx < bierz) { maxx = bierz; nr = i; } } if (maxx > 0) { cout << maxx << "\n"; for (i = 1; i < v+1; i++) if (repr[i] == nr) cout << i << " "; } else cout << "NIE"; /* for (i = 1; i < v + 1; i++) cout << i << " " << deg[i] << " " << czy[i] << "\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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include<iostream> #include <vector> #include <algorithm> using namespace std; const long long int VV=200*1000+1; vector<int> tab[VV]; int deg[VV], repr[VV]; bool czy[VV], odw[VV]; int d, v, e, maxx, nr, bierz; int lsas(int ii) {return (tab[ii].size());} int isas(int ii, int iii) {return (tab[ii][iii]);} void wyrzuc(int kk) { int ii; czy[kk] = false; for (ii = 0; ii < lsas(kk); ii++) { deg[isas(kk,ii)]--; if ( (deg[isas(kk, ii)] < d) && czy[isas(kk, ii)] ) wyrzuc(isas(kk, ii)); } return; } void odwiedz(int kk, int reprez) { int ii; if (odw[kk] == false) { odw[kk] = true; repr[kk] = reprez; bierz++; for (ii = 0; ii < lsas(kk); ii++) if (czy[isas(kk, ii)]) odwiedz(isas(kk, ii), reprez); } } int i, j, k; int main() { ios_base::sync_with_stdio(0); cin >> v >> e >> d; for (i = 0; i < e; i++) { cin >> j >> k; tab[j].push_back(k); tab[k].push_back(j); } for (i = 1; i < v + 1; i++) { czy[i] = true; deg[i] = lsas(i); repr[i] = i; odw[i] = false; } for (i = 1; i < v + 1; i++) if ( (deg[i] < d) && czy[i] ) wyrzuc(i); maxx = 0; nr = -1; for (i = 1; i < v + 1; i++) if ((odw[i] == false) && czy[i] ) { bierz = 0; odwiedz(i, i); if (maxx < bierz) { maxx = bierz; nr = i; } } if (maxx > 0) { cout << maxx << "\n"; for (i = 1; i < v+1; i++) if (repr[i] == nr) cout << i << " "; } else cout << "NIE"; /* for (i = 1; i < v + 1; i++) cout << i << " " << deg[i] << " " << czy[i] << "\n"; */ return 0; } |