#include <cstdio> #include <queue> #include <vector> #define MAXN 200003 using namespace std; int a,b,n,m,d; struct Node { int color, size; vector<int> V; } N[MAXN]; int dfs(int k, int color) { int res = 1; N[k].color = color; for(vector<int>::iterator it = N[k].V.begin(); it!=N[k].V.end(); ++it) { if(!N[*it].color && N[*it].size >= d) res += dfs(*it,color); } return res; } int main() { scanf("%d %d %d",&n,&m,&d); for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); N[a].V.push_back(b); N[b].V.push_back(a); } for(int i=1;i<=n;i++) N[i].size = N[i].V.size(); queue<int> Q; for(int i=1;i<=n;i++) if(N[i].size < d) Q.push(i); while(!Q.empty()) { int k = Q.front(); for(vector<int>::iterator it = N[k].V.begin(); it!=N[k].V.end(); ++it) { if(N[*it].size == d) Q.push(*it); N[*it].size--; } Q.pop(); } int res = 0,color; for(int i=1;i<=n;i++) if(N[i].size >= d && !N[i].color) { int r = dfs(i,i); if(r > res) { res = r; color = i; } } if(res) { printf("%d\n",res); for(int i=1;i<=n;i++) if(N[i].color == color) printf("%d ",i); printf("\n"); } else printf("NIE\n"); 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 | #include <cstdio> #include <queue> #include <vector> #define MAXN 200003 using namespace std; int a,b,n,m,d; struct Node { int color, size; vector<int> V; } N[MAXN]; int dfs(int k, int color) { int res = 1; N[k].color = color; for(vector<int>::iterator it = N[k].V.begin(); it!=N[k].V.end(); ++it) { if(!N[*it].color && N[*it].size >= d) res += dfs(*it,color); } return res; } int main() { scanf("%d %d %d",&n,&m,&d); for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); N[a].V.push_back(b); N[b].V.push_back(a); } for(int i=1;i<=n;i++) N[i].size = N[i].V.size(); queue<int> Q; for(int i=1;i<=n;i++) if(N[i].size < d) Q.push(i); while(!Q.empty()) { int k = Q.front(); for(vector<int>::iterator it = N[k].V.begin(); it!=N[k].V.end(); ++it) { if(N[*it].size == d) Q.push(*it); N[*it].size--; } Q.pop(); } int res = 0,color; for(int i=1;i<=n;i++) if(N[i].size >= d && !N[i].color) { int r = dfs(i,i); if(r > res) { res = r; color = i; } } if(res) { printf("%d\n",res); for(int i=1;i<=n;i++) if(N[i].color == color) printf("%d ",i); printf("\n"); } else printf("NIE\n"); return 0; } |