#include <cstdio> #include <map> #include <set> #include <vector> #include <cassert> int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); std::vector< std::set<int> > VS(n); while (m--) { int a, b; scanf("%d%d", &a, &b); --a; --b; VS[a].insert(b); VS[b].insert(a); } std::vector<std::pair<int,int>> G; for (int i = 0; i < n; ++i) { if (VS[i].size() < d) { for (int b : VS[i]) { G.push_back(std::make_pair(b, i)); } VS[i].clear(); } } while (!G.empty()) { int a = G.back().first; int b = G.back().second; G.pop_back(); VS[a].erase(b); if (VS[a].size() < d) { for (int i : VS[a]) { G.push_back(std::make_pair(i, a)); } VS[a].clear(); } } std::vector<int> res; for (int i = 0; i < n; ++i) { const std::set<int> &S = VS[i]; assert(S.empty() || S.size() >= d); if (S.size() >= d) { res.push_back(i + 1); } } if (res.empty()) { printf("NIE\n"); return 0; } printf("%d\n", (int) res.size()); for (int r : res) { printf("%d ", r); } 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 79 80 81 82 83 | #include <cstdio> #include <map> #include <set> #include <vector> #include <cassert> int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); std::vector< std::set<int> > VS(n); while (m--) { int a, b; scanf("%d%d", &a, &b); --a; --b; VS[a].insert(b); VS[b].insert(a); } std::vector<std::pair<int,int>> G; for (int i = 0; i < n; ++i) { if (VS[i].size() < d) { for (int b : VS[i]) { G.push_back(std::make_pair(b, i)); } VS[i].clear(); } } while (!G.empty()) { int a = G.back().first; int b = G.back().second; G.pop_back(); VS[a].erase(b); if (VS[a].size() < d) { for (int i : VS[a]) { G.push_back(std::make_pair(i, a)); } VS[a].clear(); } } std::vector<int> res; for (int i = 0; i < n; ++i) { const std::set<int> &S = VS[i]; assert(S.empty() || S.size() >= d); if (S.size() >= d) { res.push_back(i + 1); } } if (res.empty()) { printf("NIE\n"); return 0; } printf("%d\n", (int) res.size()); for (int r : res) { printf("%d ", r); } printf("\n"); return 0; } |