#include <cstdio> #include <set> #include <algorithm> std::set <int> G [200001]; bool del [200001]; bool vis [200001]; void delVertex (unsigned int v, unsigned int d) { if (del [v]) return; del [v] = 1; for (auto i : G [v]) { G [i].erase (v); if (G [i].size () < d) delVertex (i, d); } } std::vector <int> ans; void dfs (unsigned int v) { if (del [v] || vis [v]) return; vis [v] = 1; ans.push_back (v); for (auto i : G [v]) { dfs (i); } } int main () { unsigned int n, m, d; scanf ("%d %d %d", &n, &m, &d); for (unsigned int i = 0; i < m; ++ i) { int v, u; scanf ("%d %d", &v, &u); G [v].insert (u); G [u].insert (v); } for (unsigned int i = 1; i <= n; ++ i) { if (G [i].size () < d) delVertex (i, d); } std::vector <int> mx; for (unsigned int i = 1; i <= n; ++ i) { ans.clear (); dfs (i); if (ans.size () > mx.size ()) mx = ans; } std::sort (mx.begin (), mx.end ()); if (mx.size () == 0) printf ("NIE\n"); else { printf ("%d\n", int (mx.size ())); for (auto i : mx) { 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 | #include <cstdio> #include <set> #include <algorithm> std::set <int> G [200001]; bool del [200001]; bool vis [200001]; void delVertex (unsigned int v, unsigned int d) { if (del [v]) return; del [v] = 1; for (auto i : G [v]) { G [i].erase (v); if (G [i].size () < d) delVertex (i, d); } } std::vector <int> ans; void dfs (unsigned int v) { if (del [v] || vis [v]) return; vis [v] = 1; ans.push_back (v); for (auto i : G [v]) { dfs (i); } } int main () { unsigned int n, m, d; scanf ("%d %d %d", &n, &m, &d); for (unsigned int i = 0; i < m; ++ i) { int v, u; scanf ("%d %d", &v, &u); G [v].insert (u); G [u].insert (v); } for (unsigned int i = 1; i <= n; ++ i) { if (G [i].size () < d) delVertex (i, d); } std::vector <int> mx; for (unsigned int i = 1; i <= n; ++ i) { ans.clear (); dfs (i); if (ans.size () > mx.size ()) mx = ans; } std::sort (mx.begin (), mx.end ()); if (mx.size () == 0) printf ("NIE\n"); else { printf ("%d\n", int (mx.size ())); for (auto i : mx) { printf ("%d ", i); } printf ("\n"); } return 0; } |