#include <bits/stdc++.h> using namespace std; #define pb push_back #define MAXN 200001 vector <int> v[MAXN]; bool odw[MAXN]; int ile[MAXN]; int n,m,d; vector <int> wyn[MAXN]; queue <int> q; void bfs() { while(!q.empty()) { int x = q.front(); /// printf("%d\n",x); q.pop(); for(int i = 0;i < (int)v[x].size();++i) { if(!odw[v[x][i]]) { /// printf("%d %d\n",x,v[x][i]); ile[v[x][i]]--; if(ile[v[x][i]] < d) q.push(v[x][i]),odw[v[x][i]] = true; } } } } int wsk = 0; void dfs(int x) { odw[x] = true; wyn[wsk].pb(x); for(int i = 0;i < (int)v[x].size();++i) { if(!odw[v[x][i]]) dfs(v[x][i]); } } int kubelek[MAXN]; int main() { scanf("%d%d%d",&n,&m,&d); for(int i = 0;i < m;++i) { int a,b; scanf("%d%d",&a,&b); /// --a;--b; v[a].pb(b); v[b].pb(a); } for(int i = 1;i <= n;++i) { ile[i] = (int)v[i].size(); if(ile[i] < d) q.push(ile[i]), odw[i] = true; } /// for(int i =0 ;i < n;++i) printf("%d ",odw[i]); bfs(); /// puts(""); for(int i =0 ;i < n;++i) printf("%d ",odw[i]); for(int i = 1;i <= n;++i) { if(!odw[i]) dfs(i), wsk++; } int maks = 0, poz = -1; for(int i = 0;i < wsk;++i) { if(maks < (int)wyn[i].size()) maks = (int)wyn[i].size(), poz = i; } if(poz == -1) {puts("NIE");return 0;} printf("%d\n",(int)wyn[poz].size()); for(int i = 0;i < (int)wyn[poz].size();++i) kubelek[wyn[poz][i]]++; for(int i = 1;i <= n;++i) if(kubelek[i]) printf("%d ",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 | #include <bits/stdc++.h> using namespace std; #define pb push_back #define MAXN 200001 vector <int> v[MAXN]; bool odw[MAXN]; int ile[MAXN]; int n,m,d; vector <int> wyn[MAXN]; queue <int> q; void bfs() { while(!q.empty()) { int x = q.front(); /// printf("%d\n",x); q.pop(); for(int i = 0;i < (int)v[x].size();++i) { if(!odw[v[x][i]]) { /// printf("%d %d\n",x,v[x][i]); ile[v[x][i]]--; if(ile[v[x][i]] < d) q.push(v[x][i]),odw[v[x][i]] = true; } } } } int wsk = 0; void dfs(int x) { odw[x] = true; wyn[wsk].pb(x); for(int i = 0;i < (int)v[x].size();++i) { if(!odw[v[x][i]]) dfs(v[x][i]); } } int kubelek[MAXN]; int main() { scanf("%d%d%d",&n,&m,&d); for(int i = 0;i < m;++i) { int a,b; scanf("%d%d",&a,&b); /// --a;--b; v[a].pb(b); v[b].pb(a); } for(int i = 1;i <= n;++i) { ile[i] = (int)v[i].size(); if(ile[i] < d) q.push(ile[i]), odw[i] = true; } /// for(int i =0 ;i < n;++i) printf("%d ",odw[i]); bfs(); /// puts(""); for(int i =0 ;i < n;++i) printf("%d ",odw[i]); for(int i = 1;i <= n;++i) { if(!odw[i]) dfs(i), wsk++; } int maks = 0, poz = -1; for(int i = 0;i < wsk;++i) { if(maks < (int)wyn[i].size()) maks = (int)wyn[i].size(), poz = i; } if(poz == -1) {puts("NIE");return 0;} printf("%d\n",(int)wyn[poz].size()); for(int i = 0;i < (int)wyn[poz].size();++i) kubelek[wyn[poz][i]]++; for(int i = 1;i <= n;++i) if(kubelek[i]) printf("%d ",i); return 0; } |