#include <iostream> #include <algorithm> #include <set> using namespace std; struct Miasto; struct Droga { Miasto *miasto; Droga *nast; Droga(Miasto *m, Droga *d) : miasto(m), nast(d) {} }; struct Miasto { bool jest, odw; int lDrog, w; Droga *d; Miasto() : jest(true), odw(false), lDrog(0), w(-1), d(0) {} void dodaj(Miasto *sasiad) { ++lDrog; d=new Droga(sasiad, d); } } miasta[200000]; bool pm(Miasto *m1, Miasto *m2) { int r=m1->lDrog-m2->lDrog; if (r) return r<0; return m1<m2; } int ile(Miasto *m, int w) { if (!m->jest || m->odw) return 0; m->odw=true; m->w=w; int wyn=1; for (Droga *d=m->d; d; d=d->nast) wyn+=ile(d->miasto, w); return wyn; } int main() { ios_base::sync_with_stdio(false); int xn, xm, xd; cin>>xn>>xm>>xd; for (int i=0; i<xm; ++i) { int a, b; cin>>a>>b; --a; --b; miasta[a].dodaj(miasta+b); miasta[b].dodaj(miasta+a); } set<Miasto*, bool (*)(Miasto*, Miasto*)> zm(pm); for (int i=0; i<xn; ++i) zm.insert(miasta+i); while (!zm.empty()) { Miasto *m=*zm.begin(); if (xd<=m->lDrog) break; m->jest=false; zm.erase(zm.begin()); for (Droga *d=m->d; d; d=d->nast) { Miasto *mm=d->miasto; if (mm->jest) { zm.erase(mm); --mm->lDrog; zm.insert(mm); } } } int najIle=0, najW=-1; for (int i=0; i<xn; ++i) { int a=ile(miasta+i, i); if (najIle<a) { najIle=a; najW=i; } } if (najIle==0) cout<<"NIE"<<endl; else { cout<<najIle<<endl; int u[200000], uu=0; for (int i=0; i<xn; ++i) if (miasta[i].w==najW) u[uu++]=i+1; sort(u, u+uu); for (int i=0; i<najIle; ++i) cout<<u[i]<<' '; cout<<endl; } 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 101 102 103 104 105 106 107 108 109 110 111 | #include <iostream> #include <algorithm> #include <set> using namespace std; struct Miasto; struct Droga { Miasto *miasto; Droga *nast; Droga(Miasto *m, Droga *d) : miasto(m), nast(d) {} }; struct Miasto { bool jest, odw; int lDrog, w; Droga *d; Miasto() : jest(true), odw(false), lDrog(0), w(-1), d(0) {} void dodaj(Miasto *sasiad) { ++lDrog; d=new Droga(sasiad, d); } } miasta[200000]; bool pm(Miasto *m1, Miasto *m2) { int r=m1->lDrog-m2->lDrog; if (r) return r<0; return m1<m2; } int ile(Miasto *m, int w) { if (!m->jest || m->odw) return 0; m->odw=true; m->w=w; int wyn=1; for (Droga *d=m->d; d; d=d->nast) wyn+=ile(d->miasto, w); return wyn; } int main() { ios_base::sync_with_stdio(false); int xn, xm, xd; cin>>xn>>xm>>xd; for (int i=0; i<xm; ++i) { int a, b; cin>>a>>b; --a; --b; miasta[a].dodaj(miasta+b); miasta[b].dodaj(miasta+a); } set<Miasto*, bool (*)(Miasto*, Miasto*)> zm(pm); for (int i=0; i<xn; ++i) zm.insert(miasta+i); while (!zm.empty()) { Miasto *m=*zm.begin(); if (xd<=m->lDrog) break; m->jest=false; zm.erase(zm.begin()); for (Droga *d=m->d; d; d=d->nast) { Miasto *mm=d->miasto; if (mm->jest) { zm.erase(mm); --mm->lDrog; zm.insert(mm); } } } int najIle=0, najW=-1; for (int i=0; i<xn; ++i) { int a=ile(miasta+i, i); if (najIle<a) { najIle=a; najW=i; } } if (najIle==0) cout<<"NIE"<<endl; else { cout<<najIle<<endl; int u[200000], uu=0; for (int i=0; i<xn; ++i) if (miasta[i].w==najW) u[uu++]=i+1; sort(u, u+uu); for (int i=0; i<najIle; ++i) cout<<u[i]<<' '; cout<<endl; } return 0; } |