#include <iostream> #include <vector> #include <stack> int main(void) { int n; int m; int d; std::cin >> n >> m >> d; std::vector<std::vector<int>> edges(n+1); std::vector<int> edge_counts(n+1, 0); for (int i = 0; i < m; ++i) { int a; int b; std::cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); ++edge_counts[a]; ++edge_counts[b]; } std::vector<bool> run1(n+1, false); std::vector<bool> valid(n+1, false); for (int i = 1; i <= n; ++i) { if (!run1[i]) { std::stack<int> to_visit; run1[i] = true; to_visit.push(i); while (!to_visit.empty()) { int curr = to_visit.top(); to_visit.pop(); if (edge_counts[curr] >= d) { valid[curr] = true; for (int next : edges[curr]) { if (!run1[next]) { run1[next] = true; to_visit.push(next); } } } else { valid[curr] = false; for (int next : edges[curr]) { --edge_counts[next]; if (!run1[next]) { run1[next] = true; to_visit.push(next); } else if (edge_counts[next] == d - 1 && valid[next]) { to_visit.push(next); } } } } } } std::vector<bool> run2(n+1, false); std::vector<int> components(n+1, -1); int curr_component = 1; int best_component = 0; int best_component_size = 0; for (int i = 1; i <= n; ++i) { if (!run2[i]) { int curr_component_size = 0; std::stack<int> to_visit; run2[i] = true; to_visit.push(i); while (!to_visit.empty()) { int curr = to_visit.top(); to_visit.pop(); if (valid[curr]) { components[curr] = curr_component; ++curr_component_size; for (int next : edges[curr]) { if (!run2[next]) { run2[next] = true; to_visit.push(next); } } } } if (curr_component_size > best_component_size) { best_component_size = curr_component_size; best_component = curr_component; } ++curr_component; } } if (best_component_size > 0) { std::cout << best_component_size << std::endl; for (int i = 1; i <= n; ++i) { if (components[i] == best_component) { std::cout << i << " "; } } std::cout << std::endl; } else { std::cout << "NIE" << std::endl; } 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 | #include <iostream> #include <vector> #include <stack> int main(void) { int n; int m; int d; std::cin >> n >> m >> d; std::vector<std::vector<int>> edges(n+1); std::vector<int> edge_counts(n+1, 0); for (int i = 0; i < m; ++i) { int a; int b; std::cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); ++edge_counts[a]; ++edge_counts[b]; } std::vector<bool> run1(n+1, false); std::vector<bool> valid(n+1, false); for (int i = 1; i <= n; ++i) { if (!run1[i]) { std::stack<int> to_visit; run1[i] = true; to_visit.push(i); while (!to_visit.empty()) { int curr = to_visit.top(); to_visit.pop(); if (edge_counts[curr] >= d) { valid[curr] = true; for (int next : edges[curr]) { if (!run1[next]) { run1[next] = true; to_visit.push(next); } } } else { valid[curr] = false; for (int next : edges[curr]) { --edge_counts[next]; if (!run1[next]) { run1[next] = true; to_visit.push(next); } else if (edge_counts[next] == d - 1 && valid[next]) { to_visit.push(next); } } } } } } std::vector<bool> run2(n+1, false); std::vector<int> components(n+1, -1); int curr_component = 1; int best_component = 0; int best_component_size = 0; for (int i = 1; i <= n; ++i) { if (!run2[i]) { int curr_component_size = 0; std::stack<int> to_visit; run2[i] = true; to_visit.push(i); while (!to_visit.empty()) { int curr = to_visit.top(); to_visit.pop(); if (valid[curr]) { components[curr] = curr_component; ++curr_component_size; for (int next : edges[curr]) { if (!run2[next]) { run2[next] = true; to_visit.push(next); } } } } if (curr_component_size > best_component_size) { best_component_size = curr_component_size; best_component = curr_component; } ++curr_component; } } if (best_component_size > 0) { std::cout << best_component_size << std::endl; for (int i = 1; i <= n; ++i) { if (components[i] == best_component) { std::cout << i << " "; } } std::cout << std::endl; } else { std::cout << "NIE" << std::endl; } return 0; } |