#include <cstdio> #include <vector> #define PB push_back using namespace std; const int N=200*1000+5; int n, m, d, a, b, que[N], itq, sas[N]; vector<int> graf[N]; int jest[N]; void que_push(int x) { que[itq]=x; itq++; jest[x]=-1; } int DFS(int v, int nr) { int wynik=1; jest[v]=nr; for (auto j: graf[v]) { if (jest[j]==0) wynik+=DFS(j, nr); } return wynik; } int main() { scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; ++i) { scanf("%d%d", &a, &b); graf[a].PB(b); graf[b].PB(a); } for (int i=1; i<=n; ++i) { sas[i]=graf[i].size(); if (sas[i]<d) que_push(i); } for (int i=0; i<itq; ++i) { int v=que[i]; for (auto j: graf[v]) { sas[j]--; if (sas[j]==d-1) que_push(j); } } int ma=0, I=0; for (int i=1; i<=n; ++i) if (jest[i]==0) { int w=DFS(i, i); if (w>ma) { ma=w; I=i; } } if (ma==0) { printf("NIE\n"); return 0; } printf("%d\n", ma); for (int i=1; i<=n; ++i) if (jest[i]==I) printf("%d ", i); printf("\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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #include <cstdio> #include <vector> #define PB push_back using namespace std; const int N=200*1000+5; int n, m, d, a, b, que[N], itq, sas[N]; vector<int> graf[N]; int jest[N]; void que_push(int x) { que[itq]=x; itq++; jest[x]=-1; } int DFS(int v, int nr) { int wynik=1; jest[v]=nr; for (auto j: graf[v]) { if (jest[j]==0) wynik+=DFS(j, nr); } return wynik; } int main() { scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; ++i) { scanf("%d%d", &a, &b); graf[a].PB(b); graf[b].PB(a); } for (int i=1; i<=n; ++i) { sas[i]=graf[i].size(); if (sas[i]<d) que_push(i); } for (int i=0; i<itq; ++i) { int v=que[i]; for (auto j: graf[v]) { sas[j]--; if (sas[j]==d-1) que_push(j); } } int ma=0, I=0; for (int i=1; i<=n; ++i) if (jest[i]==0) { int w=DFS(i, i); if (w>ma) { ma=w; I=i; } } if (ma==0) { printf("NIE\n"); return 0; } printf("%d\n", ma); for (int i=1; i<=n; ++i) if (jest[i]==I) printf("%d ", i); printf("\n"); return 0; } |