#include<iostream> #include<vector> #include<algorithm> using namespace std; const int nMAX=200005; int n,m,d,x,y,licznik,licznikmax; bool usuniete[nMAX]; vector<int> dobre; struct miasto { vector<int> sasiedzi; int stopien; }; miasto tab[nMAX]; void usun(int a) { miasto w=tab[a]; int wx; usuniete[a]=1; for(int j=0; j<w.sasiedzi.size(); j++) if(usuniete[w.sasiedzi[j]]==0) { wx=w.sasiedzi[j]; tab[wx].stopien--; if(tab[wx].stopien<d) usun(wx); } } void dfs(int b) { dobre.push_back(b); licznik++; usuniete[b]=1; for(int k=0; k<tab[b].sasiedzi.size(); k++) if(usuniete[tab[b].sasiedzi[k]]==0) dfs(tab[b].sasiedzi[k]); } int main() { ios_base::sync_with_stdio(0); cin>>n>>m>>d; for(int i=0; i<=n; i++) tab[i].stopien=0; for(int i=0; i<m; i++) { cin>>x>>y; if(x==y) continue; tab[x].stopien++; tab[x].sasiedzi.push_back(y); tab[y].stopien++; tab[y].sasiedzi.push_back(x); } for(int i=1; i<=n; i++) if(tab[i].stopien<d && usuniete[i]==0) usun(i); //for(int i=1; i<=n; i++) //cout<<usuniete[i]; licznikmax=0; int poczatek=0; int poczatekmax=0; for(int i=1; i<=n; i++) if(usuniete[i]==0) { licznik=0; dfs(i); if(licznik>licznikmax) { licznikmax=licznik; poczatekmax=poczatek; } poczatek=poczatek+licznik; } if(licznikmax==0) { cout<<"NIE"; return 0; } vector<int>odp; for(int i=poczatekmax; i<poczatekmax+licznikmax; i++) odp.push_back(dobre[i]); sort(odp.begin(), odp.end()); cout<<odp.size()<<endl; for(int i=0; i<odp.size(); i++) cout<<odp[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 77 78 79 80 81 82 83 84 85 86 | #include<iostream> #include<vector> #include<algorithm> using namespace std; const int nMAX=200005; int n,m,d,x,y,licznik,licznikmax; bool usuniete[nMAX]; vector<int> dobre; struct miasto { vector<int> sasiedzi; int stopien; }; miasto tab[nMAX]; void usun(int a) { miasto w=tab[a]; int wx; usuniete[a]=1; for(int j=0; j<w.sasiedzi.size(); j++) if(usuniete[w.sasiedzi[j]]==0) { wx=w.sasiedzi[j]; tab[wx].stopien--; if(tab[wx].stopien<d) usun(wx); } } void dfs(int b) { dobre.push_back(b); licznik++; usuniete[b]=1; for(int k=0; k<tab[b].sasiedzi.size(); k++) if(usuniete[tab[b].sasiedzi[k]]==0) dfs(tab[b].sasiedzi[k]); } int main() { ios_base::sync_with_stdio(0); cin>>n>>m>>d; for(int i=0; i<=n; i++) tab[i].stopien=0; for(int i=0; i<m; i++) { cin>>x>>y; if(x==y) continue; tab[x].stopien++; tab[x].sasiedzi.push_back(y); tab[y].stopien++; tab[y].sasiedzi.push_back(x); } for(int i=1; i<=n; i++) if(tab[i].stopien<d && usuniete[i]==0) usun(i); //for(int i=1; i<=n; i++) //cout<<usuniete[i]; licznikmax=0; int poczatek=0; int poczatekmax=0; for(int i=1; i<=n; i++) if(usuniete[i]==0) { licznik=0; dfs(i); if(licznik>licznikmax) { licznikmax=licznik; poczatekmax=poczatek; } poczatek=poczatek+licznik; } if(licznikmax==0) { cout<<"NIE"; return 0; } vector<int>odp; for(int i=poczatekmax; i<poczatekmax+licznikmax; i++) odp.push_back(dobre[i]); sort(odp.begin(), odp.end()); cout<<odp.size()<<endl; for(int i=0; i<odp.size(); i++) cout<<odp[i]<<" "; } |