#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<bitset> using namespace std; int n, m, d; vector<int> wek[200001]; vector<int> kol; bitset<200000> dead; vector<int> odpowiedzi[200000]; int abc; int dfs(int x){ dead[x]=1; odpowiedzi[abc].push_back(x); for(int i=0;i<wek[x].size();i++){ if(!dead[wek[x][i]]) dfs(wek[x][i]); } } int main(){ scanf("%d%d%d",&n,&m,&d); int tmp1, tmp2; int ile[200001]; for(int i=0;i<m;i++){ scanf("%d%d",&tmp1,&tmp2); wek[tmp1-1].push_back(tmp2-1); wek[tmp2-1].push_back(tmp1-1); } for(int i=0;i<n;i++){ ile[i]=wek[i].size(); //cout<<"ROZMIAR "<<i+1<<" = "<<ile[i]<<endl; //cout<<ile[i]<<" <? "<<d<<endl; if(ile[i]<d){ kol.push_back(i); dead[i]=1; //cout<<"WYWALAM "<<i+1<<endl; } } int it=0; int id=0; while(it<kol.size()){ id=kol[it]; //cout<<"WYWALAM "<<id+1<<endl; for(int i=0;i<wek[id].size();i++){ if(!dead[wek[id][i]]){ ile[wek[id][i]]--; if(ile[wek[id][i]]<d){ kol.push_back(wek[id][i]); dead[wek[id][i]]=true; } } } it++; } if(it>=n){ printf("NIE"); return 0; } int maks=0; int def=-1; for(int i=0;i<n;i++){ if(!dead[i]){ dfs(i); if(maks<odpowiedzi[abc].size()){ maks=odpowiedzi[abc].size(); def=abc; } abc++; } } sort(odpowiedzi[def].begin(),odpowiedzi[def].end()); printf("%d\n",maks); for(int i=0;i<maks;i++){ printf("%d ",odpowiedzi[def][i]+1); } }
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 | #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<bitset> using namespace std; int n, m, d; vector<int> wek[200001]; vector<int> kol; bitset<200000> dead; vector<int> odpowiedzi[200000]; int abc; int dfs(int x){ dead[x]=1; odpowiedzi[abc].push_back(x); for(int i=0;i<wek[x].size();i++){ if(!dead[wek[x][i]]) dfs(wek[x][i]); } } int main(){ scanf("%d%d%d",&n,&m,&d); int tmp1, tmp2; int ile[200001]; for(int i=0;i<m;i++){ scanf("%d%d",&tmp1,&tmp2); wek[tmp1-1].push_back(tmp2-1); wek[tmp2-1].push_back(tmp1-1); } for(int i=0;i<n;i++){ ile[i]=wek[i].size(); //cout<<"ROZMIAR "<<i+1<<" = "<<ile[i]<<endl; //cout<<ile[i]<<" <? "<<d<<endl; if(ile[i]<d){ kol.push_back(i); dead[i]=1; //cout<<"WYWALAM "<<i+1<<endl; } } int it=0; int id=0; while(it<kol.size()){ id=kol[it]; //cout<<"WYWALAM "<<id+1<<endl; for(int i=0;i<wek[id].size();i++){ if(!dead[wek[id][i]]){ ile[wek[id][i]]--; if(ile[wek[id][i]]<d){ kol.push_back(wek[id][i]); dead[wek[id][i]]=true; } } } it++; } if(it>=n){ printf("NIE"); return 0; } int maks=0; int def=-1; for(int i=0;i<n;i++){ if(!dead[i]){ dfs(i); if(maks<odpowiedzi[abc].size()){ maks=odpowiedzi[abc].size(); def=abc; } abc++; } } sort(odpowiedzi[def].begin(),odpowiedzi[def].end()); printf("%d\n",maks); for(int i=0;i<maks;i++){ printf("%d ",odpowiedzi[def][i]+1); } } |