#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define PB push_back #define MP make_pair #define ST first #define ND second #define SZ(n) ((int)n.size()) const int N = 200005; int deg[N]; template<class V, class E> struct Graph { const int siz; struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; struct Ve : V, vector<Ed> { }; vector<Ve> g; Graph(int n = 0) : g(n), siz(n) {} void EdgeU(int b, int e, E d = E()) { Ed eg(d, e); eg.rev = g[b].size() + (b == e); g[b].PB(eg); eg.rev = (g[eg.v = b]).size() - 1; g[e].PB(eg); } void Bfs(int s) { for (auto& it : g) { it.t = it.s = -1; } g[s].t = 0; int qu[N]; int b, e; b = e = 0; qu[0] = s; while (b <= e) { s = qu[b++]; for (auto it : g[s]) if (g[it.v].t == -1) { int val = qu[++e] = it.v; g[val].t = (g[s].t + 1); g[it.v].s = s; } } } }; struct Ve { int rev; }; struct Vs { int t, s; }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, d, s, a, b; std::cin >> n >> m >> d; Graph<Vs, Ve> g(N); std::vector<std::pair<int, int> > pii; for (int i = 0; i < m; ++i) { cin >> a >> b; pii.PB(MP(a, b)); deg[a]++; deg[b]++; } for (int i = 0; i < m; ++i) { if (deg[pii[i].first] >= d && deg[pii[i].second] >= d) { g.EdgeU(pii[i].first, pii[i].second); } else { deg[pii[i].first]--; deg[pii[i].second]--; } } g.Bfs(1); int result = 0; std::vector<int> res; for (int x = 1; x <= n; ++x) { if (deg[x] >= d) { res.push_back(x); result++; } } if (result == 0) { cout << "NIE"; } else { cout << result << '\n'; for (int x = 0; x < res.size(); ++x) { cout << res[x] << " "; } } 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 116 117 118 119 120 | #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define PB push_back #define MP make_pair #define ST first #define ND second #define SZ(n) ((int)n.size()) const int N = 200005; int deg[N]; template<class V, class E> struct Graph { const int siz; struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) { } }; struct Ve : V, vector<Ed> { }; vector<Ve> g; Graph(int n = 0) : g(n), siz(n) {} void EdgeU(int b, int e, E d = E()) { Ed eg(d, e); eg.rev = g[b].size() + (b == e); g[b].PB(eg); eg.rev = (g[eg.v = b]).size() - 1; g[e].PB(eg); } void Bfs(int s) { for (auto& it : g) { it.t = it.s = -1; } g[s].t = 0; int qu[N]; int b, e; b = e = 0; qu[0] = s; while (b <= e) { s = qu[b++]; for (auto it : g[s]) if (g[it.v].t == -1) { int val = qu[++e] = it.v; g[val].t = (g[s].t + 1); g[it.v].s = s; } } } }; struct Ve { int rev; }; struct Vs { int t, s; }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, d, s, a, b; std::cin >> n >> m >> d; Graph<Vs, Ve> g(N); std::vector<std::pair<int, int> > pii; for (int i = 0; i < m; ++i) { cin >> a >> b; pii.PB(MP(a, b)); deg[a]++; deg[b]++; } for (int i = 0; i < m; ++i) { if (deg[pii[i].first] >= d && deg[pii[i].second] >= d) { g.EdgeU(pii[i].first, pii[i].second); } else { deg[pii[i].first]--; deg[pii[i].second]--; } } g.Bfs(1); int result = 0; std::vector<int> res; for (int x = 1; x <= n; ++x) { if (deg[x] >= d) { res.push_back(x); result++; } } if (result == 0) { cout << "NIE"; } else { cout << result << '\n'; for (int x = 0; x < res.size(); ++x) { cout << res[x] << " "; } } return 0; } |