#include<bits/stdc++.h> using namespace std; vector<int> v[200009]; int ts[200009]; bool tb[200009],tus[200009]; list<int> lista; vector<int> wyn,w2; void dfs(int x) { tb[x]=true; w2.push_back(x); for(vector<int>::iterator it=v[x].begin();it!=v[x].end();++it) if(!tb[*it] && !tus[*it]) dfs(*it); } int main() { int n,m,d,a,b; scanf("%d%d%d",&n,&m,&d); for(int i=0;i<m;++i) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } for(int i=1;i<=n;++i) { ts[i]=v[i].size(); if(ts[i]<d) { tus[i]=true; lista.push_back(i); } } while(!lista.empty()) { a=lista.front(); lista.pop_front(); //printf("%d\n",a); for(vector<int>::iterator it=v[a].begin();it!=v[a].end();++it) if(!tus[*it]) { --ts[*it]; if(ts[*it]<d) { tus[*it]=true; lista.push_back(*it); } } } for(int i=1;i<=n;++i) if(!tb[i] && !tus[i]) { dfs(i); if(w2.size()>wyn.size()) wyn=w2; } if(!wyn.empty()) { sort(wyn.begin(),wyn.end()); printf("%d\n",wyn.size()); for(vector<int>::iterator it=wyn.begin();it!=wyn.end();++it) printf("%d ",*it); } else printf("NIE"); 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 | #include<bits/stdc++.h> using namespace std; vector<int> v[200009]; int ts[200009]; bool tb[200009],tus[200009]; list<int> lista; vector<int> wyn,w2; void dfs(int x) { tb[x]=true; w2.push_back(x); for(vector<int>::iterator it=v[x].begin();it!=v[x].end();++it) if(!tb[*it] && !tus[*it]) dfs(*it); } int main() { int n,m,d,a,b; scanf("%d%d%d",&n,&m,&d); for(int i=0;i<m;++i) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } for(int i=1;i<=n;++i) { ts[i]=v[i].size(); if(ts[i]<d) { tus[i]=true; lista.push_back(i); } } while(!lista.empty()) { a=lista.front(); lista.pop_front(); //printf("%d\n",a); for(vector<int>::iterator it=v[a].begin();it!=v[a].end();++it) if(!tus[*it]) { --ts[*it]; if(ts[*it]<d) { tus[*it]=true; lista.push_back(*it); } } } for(int i=1;i<=n;++i) if(!tb[i] && !tus[i]) { dfs(i); if(w2.size()>wyn.size()) wyn=w2; } if(!wyn.empty()) { sort(wyn.begin(),wyn.end()); printf("%d\n",wyn.size()); for(vector<int>::iterator it=wyn.begin();it!=wyn.end();++it) printf("%d ",*it); } else printf("NIE"); return 0; } |