#include<bits/stdc++.h> using namespace std; vector<int>v[200001]; set<int>wynik; int ile[200001]; queue<int>q; vector<vector<int> >v2; bool queued[200001]; int n,m,a,b,d; int main() { cin>>n>>m>>d; for(int i=0;i<m;i++) { cin>>a>>b; ile[a]++; ile[b]++; v[a].push_back(b); v[b].push_back(a); } for(int i=1;i<=n;i++) { if(ile[i]<d) { q.push(i); queued[i]=true; } } while(!q.empty()) { for(int i=0;i<v[q.front()].size();i++) { ile[v[q.front()][i]]--; //cout<<v[q.front()][i]<<" "<<ile[v[q.front()][i]]<<"\n"; if(!queued[v[q.front()][i]] && ile[v[q.front()][i]]<d) { q.push(v[q.front()][i]); queued[v[q.front()][i]]=true; } } q.pop(); } // if(queued[2])cout<<"tak\n";else cout<<"nie\n"; int i2=1; v2.resize(i2); for(int i=1;i<=n;i++) { if(!queued[i]) { q.push(i); queued[i]=true; while(!q.empty()) { v2.back().push_back(q.front()); for(int i3=0;i3<v[q.front()].size();i3++) { if(!queued[v[q.front()][i3]]) { q.push(v[q.front()][i3]); queued[v[q.front()][i3]]=true; } } q.pop(); } i2++; v2.resize(i2); } } int imaks=0; int maks=0; for(int i=0;i<i2;i++) { if(v2[i].size()>maks) { maks=v2[i].size(); imaks=i; } } if(maks==0){cout<<"NIE";return 0;} cout<<maks<<"\n"; sort(v2[imaks].begin(),v2[imaks].end()); for(int i=0;i<v2[imaks].size();i++) cout<<v2[imaks][i]<<" "; cout<<"\n"; }
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 | #include<bits/stdc++.h> using namespace std; vector<int>v[200001]; set<int>wynik; int ile[200001]; queue<int>q; vector<vector<int> >v2; bool queued[200001]; int n,m,a,b,d; int main() { cin>>n>>m>>d; for(int i=0;i<m;i++) { cin>>a>>b; ile[a]++; ile[b]++; v[a].push_back(b); v[b].push_back(a); } for(int i=1;i<=n;i++) { if(ile[i]<d) { q.push(i); queued[i]=true; } } while(!q.empty()) { for(int i=0;i<v[q.front()].size();i++) { ile[v[q.front()][i]]--; //cout<<v[q.front()][i]<<" "<<ile[v[q.front()][i]]<<"\n"; if(!queued[v[q.front()][i]] && ile[v[q.front()][i]]<d) { q.push(v[q.front()][i]); queued[v[q.front()][i]]=true; } } q.pop(); } // if(queued[2])cout<<"tak\n";else cout<<"nie\n"; int i2=1; v2.resize(i2); for(int i=1;i<=n;i++) { if(!queued[i]) { q.push(i); queued[i]=true; while(!q.empty()) { v2.back().push_back(q.front()); for(int i3=0;i3<v[q.front()].size();i3++) { if(!queued[v[q.front()][i3]]) { q.push(v[q.front()][i3]); queued[v[q.front()][i3]]=true; } } q.pop(); } i2++; v2.resize(i2); } } int imaks=0; int maks=0; for(int i=0;i<i2;i++) { if(v2[i].size()>maks) { maks=v2[i].size(); imaks=i; } } if(maks==0){cout<<"NIE";return 0;} cout<<maks<<"\n"; sort(v2[imaks].begin(),v2[imaks].end()); for(int i=0;i<v2[imaks].size();i++) cout<<v2[imaks][i]<<" "; cout<<"\n"; } |