#include<iostream> #include<algorithm> #include<set> #include<vector> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back using namespace std; vector<int>v[200000]; bool jest[200000]; set<PII>deg; int stop[200000]; void zmniejsz(int x){ deg.erase(mp(stop[x],x)); stop[x]--; deg.insert(mp(stop[x],x)); } bool odw[200000]; int dfs(int x){ int w=1; odw[x]=1; for(int i=0;i<v[x].size();i++){ if(odw[v[x][i]]||!jest[v[x][i]])continue; w+=dfs(v[x][i]); } return w; } main(){ ios_base::sync_with_stdio(0); int n,m,d; cin>>n>>m>>d; for(int i=0;i<n;i++)jest[i]=1; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--;b--; v[a].pb(b); v[b].pb(a); stop[a]++; stop[b]++; } for(int i=0;i<n;i++)deg.insert(mp(stop[i],i)); while(deg.size()>0){ if(deg.begin()->st>=d)break; int w=deg.begin()->nd; jest[w]=0; deg.erase(mp(stop[w],w)); for(int j=0;j<v[w].size();j++){ if(jest[v[w][j]])zmniejsz(v[w][j]); } } if(deg.size()==0){ cout<<"NIE\n"; return 0; } int wyn=0,st=-1; for(int i=0;i<n;i++){ if(!odw[i]&&jest[i]){ int akt=dfs(i); if(akt>wyn){ wyn=akt; st=i; } } } for(int i=0;i<n;i++)odw[i]=0; dfs(st); cout<<wyn<<"\n"; for(int i=0;i<n;i++){ if(odw[i])cout<<i+1<<" "; } 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 | #include<iostream> #include<algorithm> #include<set> #include<vector> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back using namespace std; vector<int>v[200000]; bool jest[200000]; set<PII>deg; int stop[200000]; void zmniejsz(int x){ deg.erase(mp(stop[x],x)); stop[x]--; deg.insert(mp(stop[x],x)); } bool odw[200000]; int dfs(int x){ int w=1; odw[x]=1; for(int i=0;i<v[x].size();i++){ if(odw[v[x][i]]||!jest[v[x][i]])continue; w+=dfs(v[x][i]); } return w; } main(){ ios_base::sync_with_stdio(0); int n,m,d; cin>>n>>m>>d; for(int i=0;i<n;i++)jest[i]=1; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--;b--; v[a].pb(b); v[b].pb(a); stop[a]++; stop[b]++; } for(int i=0;i<n;i++)deg.insert(mp(stop[i],i)); while(deg.size()>0){ if(deg.begin()->st>=d)break; int w=deg.begin()->nd; jest[w]=0; deg.erase(mp(stop[w],w)); for(int j=0;j<v[w].size();j++){ if(jest[v[w][j]])zmniejsz(v[w][j]); } } if(deg.size()==0){ cout<<"NIE\n"; return 0; } int wyn=0,st=-1; for(int i=0;i<n;i++){ if(!odw[i]&&jest[i]){ int akt=dfs(i); if(akt>wyn){ wyn=akt; st=i; } } } for(int i=0;i<n;i++)odw[i]=0; dfs(st); cout<<wyn<<"\n"; for(int i=0;i<n;i++){ if(odw[i])cout<<i+1<<" "; } cout<<"\n"; } |