#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int N=200*1000+7; vector<int> gr[N]; vector<int> wyn[N]; int st[N]; bool odw[N]; int d; void remove(int w) { odw[w] = 1; for (int i : gr[w]) { st[i]--; if (!odw[i] && st[i]<d) remove(i); } } void agregate(int w, int flag) { odw[w] = 1; wyn[flag].push_back(w); for (int i : gr[w]) if (!odw[i]) agregate(i, flag); } int main () { int n, m; scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); gr[a].push_back(b); gr[b].push_back(a); st[a]++; st[b]++; } for (int i=1; i<=n; i++) if (!odw[i] && st[i]<d) remove(i); int best = 0; for (int i=1; i<=n; i++) { if (!odw[i]) agregate(i, i); if (wyn[best].size() < wyn[i].size()) best = i; } if (best == 0) { printf ("NIE\n"); return 0; } vector<int>& cur = wyn[best]; sort (cur.begin(), cur.end()); printf ("%zu\n", cur.size()); for (int w : cur) printf ("%d ", w); 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int N=200*1000+7; vector<int> gr[N]; vector<int> wyn[N]; int st[N]; bool odw[N]; int d; void remove(int w) { odw[w] = 1; for (int i : gr[w]) { st[i]--; if (!odw[i] && st[i]<d) remove(i); } } void agregate(int w, int flag) { odw[w] = 1; wyn[flag].push_back(w); for (int i : gr[w]) if (!odw[i]) agregate(i, flag); } int main () { int n, m; scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); gr[a].push_back(b); gr[b].push_back(a); st[a]++; st[b]++; } for (int i=1; i<=n; i++) if (!odw[i] && st[i]<d) remove(i); int best = 0; for (int i=1; i<=n; i++) { if (!odw[i]) agregate(i, i); if (wyn[best].size() < wyn[i].size()) best = i; } if (best == 0) { printf ("NIE\n"); return 0; } vector<int>& cur = wyn[best]; sort (cur.begin(), cur.end()); printf ("%zu\n", cur.size()); for (int w : cur) printf ("%d ", w); printf("\n"); return 0; } |