#include <algorithm> #include <cstdio> #include <queue> #include <vector> using namespace std; const int MAXN = 2e5; struct Vertex { int degree; int ind; bool deleted; vector<int> neighbours; bool operator<(const Vertex& o) const { return degree < o.degree; } } graph[MAXN + 1]; int old_ind2new_ind[MAXN + 1]; queue<int> delete_queue; int deleted_cnt = 0; int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); graph[a].neighbours.push_back(b); graph[b].neighbours.push_back(a); } for (int i = 1; i <= n; i++) { auto& v = graph[i]; v.ind = i; v.degree = v.neighbours.size(); v.deleted = false; } sort(graph + 1, graph + n + 1); for (int i = 1; i <= n; i++) old_ind2new_ind[graph[i].ind] = i; for (int i = 1; i <= n; i++) { Vertex& v = graph[i]; if (v.degree >= d) break; delete_queue.push(v.ind); } while (!delete_queue.empty()) { int ind = old_ind2new_ind[delete_queue.front()]; delete_queue.pop(); Vertex& v = graph[ind]; if (v.deleted) continue; if (v.degree >= d) break; v.deleted = true; deleted_cnt++; for (int neighbour_ind : v.neighbours) { neighbour_ind = old_ind2new_ind[neighbour_ind]; if (!graph[neighbour_ind].deleted && --graph[neighbour_ind].degree < d) delete_queue.push(graph[neighbour_ind].ind); } } if (deleted_cnt == n) printf("NIE\n"); else { printf("%d\n", n - deleted_cnt); sort(graph + 1, graph + n + 1, [](const Vertex& a, const Vertex& b) { return a.ind < b.ind; }); for (int i = 1; i <= n; i++) { Vertex& v = graph[i]; if (!v.deleted) printf("%d ", v.ind); } } 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 <algorithm> #include <cstdio> #include <queue> #include <vector> using namespace std; const int MAXN = 2e5; struct Vertex { int degree; int ind; bool deleted; vector<int> neighbours; bool operator<(const Vertex& o) const { return degree < o.degree; } } graph[MAXN + 1]; int old_ind2new_ind[MAXN + 1]; queue<int> delete_queue; int deleted_cnt = 0; int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); graph[a].neighbours.push_back(b); graph[b].neighbours.push_back(a); } for (int i = 1; i <= n; i++) { auto& v = graph[i]; v.ind = i; v.degree = v.neighbours.size(); v.deleted = false; } sort(graph + 1, graph + n + 1); for (int i = 1; i <= n; i++) old_ind2new_ind[graph[i].ind] = i; for (int i = 1; i <= n; i++) { Vertex& v = graph[i]; if (v.degree >= d) break; delete_queue.push(v.ind); } while (!delete_queue.empty()) { int ind = old_ind2new_ind[delete_queue.front()]; delete_queue.pop(); Vertex& v = graph[ind]; if (v.deleted) continue; if (v.degree >= d) break; v.deleted = true; deleted_cnt++; for (int neighbour_ind : v.neighbours) { neighbour_ind = old_ind2new_ind[neighbour_ind]; if (!graph[neighbour_ind].deleted && --graph[neighbour_ind].degree < d) delete_queue.push(graph[neighbour_ind].ind); } } if (deleted_cnt == n) printf("NIE\n"); else { printf("%d\n", n - deleted_cnt); sort(graph + 1, graph + n + 1, [](const Vertex& a, const Vertex& b) { return a.ind < b.ind; }); for (int i = 1; i <= n; i++) { Vertex& v = graph[i]; if (!v.deleted) printf("%d ", v.ind); } } return 0; } |