#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int c [210000]; vector <int> V[210000]; vector <int> zbiory [210000]; queue <int> Q; queue <int> B; int active [210000]; int odw[210000]; int maks=-1; int stan=0; int main() { int n,m,d,a,b; scanf("%d %d %d", &n,&m,&d); for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); V[a].push_back(b); V[b].push_back(a); } for (int i=1;i<=n;i++) { c[i]=V[i].size(); } for(int i =1;i<=n;i++) { if(c[i]<d) { if(active[i]==0) { Q.push(i); active[i]=-1; } } } while(!Q.empty()) { int r = Q.front(); Q.pop(); for(int i=0;i<V[r].size();i++) { c[V[r][i]]--; if(c[V[r][i]] <d && active[V[r][i]] == 0) { Q.push(V[r][i]); active[V[r][i]]=-1; } } } /* for(int i=1;i<10;i++) { printf("%d",active[i]); }*/ for(int i=1;i<=n;i++) { if(odw[i]==0 && active[i]==0) { stan=1; int indeks=i; B.push(i); odw[i]=1; while(!B.empty()) { int akt = B.front(); zbiory[indeks].push_back(akt); B.pop(); for(int j=0;j<V[akt].size();j++) { if(odw[V[akt][j]]==0 && active[V[akt][j]]==0) { odw[V[akt][j]]=1; B.push(V[akt][j]); } } } } } if(stan) { maks=-1; for(int i=1;i<=n;i++) { maks=max(maks,(int)zbiory[i].size()); } for(int i=1;i<=n;i++) { if(maks==zbiory[i].size()) { sort(zbiory[i].begin(),zbiory[i].end()); printf("%d\n",maks); for(int j=0;j<zbiory[i].size();j++) { printf("%d ",zbiory[i][j]); } break; } } } else { printf("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 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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int c [210000]; vector <int> V[210000]; vector <int> zbiory [210000]; queue <int> Q; queue <int> B; int active [210000]; int odw[210000]; int maks=-1; int stan=0; int main() { int n,m,d,a,b; scanf("%d %d %d", &n,&m,&d); for(int i=0;i<m;i++) { scanf("%d %d",&a,&b); V[a].push_back(b); V[b].push_back(a); } for (int i=1;i<=n;i++) { c[i]=V[i].size(); } for(int i =1;i<=n;i++) { if(c[i]<d) { if(active[i]==0) { Q.push(i); active[i]=-1; } } } while(!Q.empty()) { int r = Q.front(); Q.pop(); for(int i=0;i<V[r].size();i++) { c[V[r][i]]--; if(c[V[r][i]] <d && active[V[r][i]] == 0) { Q.push(V[r][i]); active[V[r][i]]=-1; } } } /* for(int i=1;i<10;i++) { printf("%d",active[i]); }*/ for(int i=1;i<=n;i++) { if(odw[i]==0 && active[i]==0) { stan=1; int indeks=i; B.push(i); odw[i]=1; while(!B.empty()) { int akt = B.front(); zbiory[indeks].push_back(akt); B.pop(); for(int j=0;j<V[akt].size();j++) { if(odw[V[akt][j]]==0 && active[V[akt][j]]==0) { odw[V[akt][j]]=1; B.push(V[akt][j]); } } } } } if(stan) { maks=-1; for(int i=1;i<=n;i++) { maks=max(maks,(int)zbiory[i].size()); } for(int i=1;i<=n;i++) { if(maks==zbiory[i].size()) { sort(zbiory[i].begin(),zbiory[i].end()); printf("%d\n",maks); for(int j=0;j<zbiory[i].size();j++) { printf("%d ",zbiory[i][j]); } break; } } } else { printf("NIE"); } return 0; } |