#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n,m,d,x,y,w,i,fi,fr,q[200200],v[200200]; vector<int> g[200200],c[200200]; bool u[200200]; void dfs(int x) { u[x]=true; c[i].push_back(x); for (int j=0; j<g[x].size(); j++) { int y=g[x][j]; if (v[y]>=d && !u[y]) dfs(y); } } int main() { scanf("%d%d%d",&n,&m,&d); while (m--) { scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } for (i=1; i<=n; i++) { v[i]=g[i].size(); if (v[i]<d) q[fr++]=i; } while (fi<fr) { i=q[fi++]; for (x=0; x<g[i].size(); x++) { y=g[i][x]; if (v[y]--==d) q[fr++]=y; } } for (i=1; i<=n; i++) if (v[i]>=d && !u[i]) { dfs(i); if (c[i].size()>c[w].size()) w=i; } if (c[w].size()) { m=c[w].size(); printf("%d\n",m); sort(c[w].begin(),c[w].end()); for (i=0; i<m; i++) printf("%d%c",c[w][i],(i==m-1)?'\n':' '); } else puts("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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n,m,d,x,y,w,i,fi,fr,q[200200],v[200200]; vector<int> g[200200],c[200200]; bool u[200200]; void dfs(int x) { u[x]=true; c[i].push_back(x); for (int j=0; j<g[x].size(); j++) { int y=g[x][j]; if (v[y]>=d && !u[y]) dfs(y); } } int main() { scanf("%d%d%d",&n,&m,&d); while (m--) { scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } for (i=1; i<=n; i++) { v[i]=g[i].size(); if (v[i]<d) q[fr++]=i; } while (fi<fr) { i=q[fi++]; for (x=0; x<g[i].size(); x++) { y=g[i][x]; if (v[y]--==d) q[fr++]=y; } } for (i=1; i<=n; i++) if (v[i]>=d && !u[i]) { dfs(i); if (c[i].size()>c[w].size()) w=i; } if (c[w].size()) { m=c[w].size(); printf("%d\n",m); sort(c[w].begin(),c[w].end()); for (i=0; i<m; i++) printf("%d%c",c[w][i],(i==m-1)?'\n':' '); } else puts("NIE"); return 0; } |