#include<cstdio> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> G[200008]; int val[200008]; bool vis[200008]; queue<int> Q; vector<int> V; int BFS(int x){ queue<int> q; q.push(x); int c=0; while(!q.empty()){ int a=q.front(); q.pop(); if(vis[a])continue; vis[a]=true; c++; V.push_back(a); for(int i=0;i<G[a].size();i++)if(!vis[G[a][i]])q.push(G[a][i]); } return c; } main(){ int n,m,d; scanf("%d%d%d",&n,&m,&d); for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } for(int i=0;i<=n;i++){ val[i]=G[i].size(); if(val[i]<d){ Q.push(i); vis[i]=true; } } while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();i++){ val[G[x][i]]--; if(!vis[G[x][i]] && val[G[x][i]]<d){ Q.push(G[x][i]); vis[G[x][i]]=true; } } } int curM=0,c=0; vector<int> curV; curV.clear(); V.clear(); for(int i=1;i<=n;i++){ if(!vis[i])c=BFS(i); if(c>curM){ curV=V; curM=c; } V.clear(); } sort(curV.begin(),curV.end()); if(curM){ printf("%d\n",curM); for(int i=0;i<curV.size();i++)printf("%d ",curV[i]); printf("\n"); } else printf("NIE\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 | #include<cstdio> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> G[200008]; int val[200008]; bool vis[200008]; queue<int> Q; vector<int> V; int BFS(int x){ queue<int> q; q.push(x); int c=0; while(!q.empty()){ int a=q.front(); q.pop(); if(vis[a])continue; vis[a]=true; c++; V.push_back(a); for(int i=0;i<G[a].size();i++)if(!vis[G[a][i]])q.push(G[a][i]); } return c; } main(){ int n,m,d; scanf("%d%d%d",&n,&m,&d); for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } for(int i=0;i<=n;i++){ val[i]=G[i].size(); if(val[i]<d){ Q.push(i); vis[i]=true; } } while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();i++){ val[G[x][i]]--; if(!vis[G[x][i]] && val[G[x][i]]<d){ Q.push(G[x][i]); vis[G[x][i]]=true; } } } int curM=0,c=0; vector<int> curV; curV.clear(); V.clear(); for(int i=1;i<=n;i++){ if(!vis[i])c=BFS(i); if(c>curM){ curV=V; curM=c; } V.clear(); } sort(curV.begin(),curV.end()); if(curM){ printf("%d\n",curM); for(int i=0;i<curV.size();i++)printf("%d ",curV[i]); printf("\n"); } else printf("NIE\n"); } |