#include <stdint.h> #include <iostream> #include <vector> #include <queue> const int32_t MAX = 200001; struct { std::vector<int32_t> edges; bool inQueue{false}; int32_t color{0}; int32_t size{0}; } G[MAX]; int32_t a, b, k, m, n; std::queue<int32_t> Q; int32_t dfs(int32_t begin, int32_t sccID) { G[begin].color = sccID; int32_t size = 1; for(auto &v : G[begin].edges) { if(!G[v].color && !G[v].inQueue) size += dfs(v, sccID); } return size; } void run(void) { std::cin >> n >> m >> k; for(int32_t i = 0; i < m; ++i) { std::cin >> a >> b; G[a-1].edges.push_back(b-1); G[b-1].edges.push_back(a-1); } for(int32_t i = 0; i < n; ++i) { G[i].size = G[i].edges.size(); if(G[i].edges.size() < k) { G[i].inQueue = true; Q.push(i); } } while(!Q.empty()) { int32_t current = Q.front(); Q.pop(); int32_t tmp = 0; for(auto &v : G[current].edges) { G[v].size --; if(G[v].inQueue) continue; if(G[v].size < k) { G[v].inQueue = true; Q.push(v); } } } int32_t maxValue, maxID, tmp; maxValue = maxID = -1; for(int32_t i = 0; i < n; ++i) { if(!G[i].color && !G[i].inQueue) { tmp = dfs(i, i+1); if(tmp > maxValue) { maxValue = tmp; maxID = i+1; } } } if(maxValue == -1) { std::cout << "NIE" << std::endl; return; } std::cout << tmp << std::endl; for(int32_t i = 0; i < n; ++i) { if(G[i].color == maxID) std::cout << i+1 << " "; } std::cout << std::endl; } int main(void) { std::ios_base::sync_with_stdio(false); run(); 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 | #include <stdint.h> #include <iostream> #include <vector> #include <queue> const int32_t MAX = 200001; struct { std::vector<int32_t> edges; bool inQueue{false}; int32_t color{0}; int32_t size{0}; } G[MAX]; int32_t a, b, k, m, n; std::queue<int32_t> Q; int32_t dfs(int32_t begin, int32_t sccID) { G[begin].color = sccID; int32_t size = 1; for(auto &v : G[begin].edges) { if(!G[v].color && !G[v].inQueue) size += dfs(v, sccID); } return size; } void run(void) { std::cin >> n >> m >> k; for(int32_t i = 0; i < m; ++i) { std::cin >> a >> b; G[a-1].edges.push_back(b-1); G[b-1].edges.push_back(a-1); } for(int32_t i = 0; i < n; ++i) { G[i].size = G[i].edges.size(); if(G[i].edges.size() < k) { G[i].inQueue = true; Q.push(i); } } while(!Q.empty()) { int32_t current = Q.front(); Q.pop(); int32_t tmp = 0; for(auto &v : G[current].edges) { G[v].size --; if(G[v].inQueue) continue; if(G[v].size < k) { G[v].inQueue = true; Q.push(v); } } } int32_t maxValue, maxID, tmp; maxValue = maxID = -1; for(int32_t i = 0; i < n; ++i) { if(!G[i].color && !G[i].inQueue) { tmp = dfs(i, i+1); if(tmp > maxValue) { maxValue = tmp; maxID = i+1; } } } if(maxValue == -1) { std::cout << "NIE" << std::endl; return; } std::cout << tmp << std::endl; for(int32_t i = 0; i < n; ++i) { if(G[i].color == maxID) std::cout << i+1 << " "; } std::cout << std::endl; } int main(void) { std::ios_base::sync_with_stdio(false); run(); return 0; } |