#include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; vector<int>g[200001]; int ile[200001]; bool usun[200001]; int main(){ int n,m,d; int a,b; cin>>n>>m>>d; while(m--){ cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } for(int i=1;i<=n;i++) ile[i]=g[i].size(); vector<int>t; for(int i =1;i<=n;i++) if(ile[i]<d){ usun[i]=true; for(int j =0;j<g[i].size();j++){ ile[g[i][j]]--; if(ile[g[i][j]]<d and usun[g[i][j]]==false) t.push_back(g[i][j]); } ile[i]=0; g[i].clear(); } for(int i=0;i<t.size();i++) if(usun[t[i]]==false){ usun[t[i]]=true; for(int j =0;j<g[t[i]].size();j++){ ile[g[t[i]][j]]--; if(ile[g[t[i]][j]]<d and usun[g[t[i]][j]]==false) t.push_back(g[t[i]][j]); } ile[t[i]]=0; g[t[i]].clear(); } for(int i =1;i<=n;i++) if(usun[i]==false){ for(int j=0;j<g[i].size();j++) if(usun[g[i][j]]==true){ g[i][j]=g[i][g[i].size()-1]; g[i].pop_back(); j--; } } bool vis[200001]; int s[200000]; int maks = 0; int mm=-1; vector<int>ska; deque<int>kol; for(int i=1;i<=n;i++){ int wynik = 0; if(vis[i]==false and usun[i]==false){ // s++; vis[i]=true; kol.push_back(i); while(!kol.empty()){ int a = kol.front(); s[a]=i; kol.pop_front(); wynik++; for(int j=0;j<g[a].size();j++){ if(vis[g[a][j]]==false){ vis[g[a][j]]=true; kol.push_back(g[a][j]); } } } if(wynik>maks){ maks = wynik; mm = i; } } } if(mm==-1){ cout<<"NIE\n"; }else{ cout<<maks<<"\n"; for(int i=1;i<=n;i++) if(s[i]==mm) cout<<i<<" "; } 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 112 113 114 115 116 117 118 119 120 121 122 123 | #include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; vector<int>g[200001]; int ile[200001]; bool usun[200001]; int main(){ int n,m,d; int a,b; cin>>n>>m>>d; while(m--){ cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } for(int i=1;i<=n;i++) ile[i]=g[i].size(); vector<int>t; for(int i =1;i<=n;i++) if(ile[i]<d){ usun[i]=true; for(int j =0;j<g[i].size();j++){ ile[g[i][j]]--; if(ile[g[i][j]]<d and usun[g[i][j]]==false) t.push_back(g[i][j]); } ile[i]=0; g[i].clear(); } for(int i=0;i<t.size();i++) if(usun[t[i]]==false){ usun[t[i]]=true; for(int j =0;j<g[t[i]].size();j++){ ile[g[t[i]][j]]--; if(ile[g[t[i]][j]]<d and usun[g[t[i]][j]]==false) t.push_back(g[t[i]][j]); } ile[t[i]]=0; g[t[i]].clear(); } for(int i =1;i<=n;i++) if(usun[i]==false){ for(int j=0;j<g[i].size();j++) if(usun[g[i][j]]==true){ g[i][j]=g[i][g[i].size()-1]; g[i].pop_back(); j--; } } bool vis[200001]; int s[200000]; int maks = 0; int mm=-1; vector<int>ska; deque<int>kol; for(int i=1;i<=n;i++){ int wynik = 0; if(vis[i]==false and usun[i]==false){ // s++; vis[i]=true; kol.push_back(i); while(!kol.empty()){ int a = kol.front(); s[a]=i; kol.pop_front(); wynik++; for(int j=0;j<g[a].size();j++){ if(vis[g[a][j]]==false){ vis[g[a][j]]=true; kol.push_back(g[a][j]); } } } if(wynik>maks){ maks = wynik; mm = i; } } } if(mm==-1){ cout<<"NIE\n"; }else{ cout<<maks<<"\n"; for(int i=1;i<=n;i++) if(s[i]==mm) cout<<i<<" "; } return 0; } |