#include <iostream> #include <vector> #include <queue> #include <sstream> using namespace std; const int NO_ANS = -1; typedef int vertex_id; typedef vector<vertex_id> edges_t; typedef vector<edges_t> graph_t; void trim(const graph_t& g, vector<bool>& disc, vector<int>& deg, vertex_id v, int deg_tres) { queue<int> q; vertex_id c, n; disc[v] = true; q.push(v); while (!q.empty()) { c = q.front(); q.pop(); for (int i = 0; i < (int) g[c].size(); ++i) { n = g[c][i]; --deg[n]; if (!disc[n] && deg[n] < deg_tres) { disc[n] = true; q.push(n); } } } } int gsize(const graph_t& g, vector<bool>& disc, vector<int>& deg, vertex_id v) { int res = 0; queue<int> q; vertex_id c, n; deg[v] = v; q.push(v); ++res; while (!q.empty()) { c = q.front(); q.pop(); for (int i = 0; i < (int) g[c].size(); ++i) { n = g[c][i]; if (!disc[n] && deg[n] == NO_ANS) { deg[n] = v; q.push(n); ++res; } } } return res; } int main() { ios_base::sync_with_stdio(0); vertex_id v; vertex_id e; int deg_tres; cin >> v >> e >> deg_tres; graph_t g(v); vector<int> deg(v, 0); vector<bool> disc(v, 0); int a, b; for (int i = 0; i < e; ++i) { cin >> a >> b; --a; --b; g[a].push_back(b); g[b].push_back(a); ++deg[a]; ++deg[b]; } for (int i = 0; i < v; ++i) { if (!disc[i] && (int) g[i].size() < deg_tres) { trim(g, disc, deg, i, deg_tres); } } for (int i = 0; i < v; ++i) { deg[i] = NO_ANS; } int best_tag = NO_ANS; int best_size = -1; int cur_size; for (int i = 0; i < v; ++i) { if (!disc[i] && deg[i] == NO_ANS) { cur_size = gsize(g, disc, deg, i); if (best_size < cur_size) { best_size = cur_size; best_tag = i; } } } if (best_tag == NO_ANS) { cout << "NIE" << endl; } else { cout << best_size << endl; for (int i = 0; i < v; ++i) { if (deg[i] == best_tag) { cout << (i + 1) << " "; } } cout << 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 110 111 112 113 114 115 116 117 118 119 120 121 | #include <iostream> #include <vector> #include <queue> #include <sstream> using namespace std; const int NO_ANS = -1; typedef int vertex_id; typedef vector<vertex_id> edges_t; typedef vector<edges_t> graph_t; void trim(const graph_t& g, vector<bool>& disc, vector<int>& deg, vertex_id v, int deg_tres) { queue<int> q; vertex_id c, n; disc[v] = true; q.push(v); while (!q.empty()) { c = q.front(); q.pop(); for (int i = 0; i < (int) g[c].size(); ++i) { n = g[c][i]; --deg[n]; if (!disc[n] && deg[n] < deg_tres) { disc[n] = true; q.push(n); } } } } int gsize(const graph_t& g, vector<bool>& disc, vector<int>& deg, vertex_id v) { int res = 0; queue<int> q; vertex_id c, n; deg[v] = v; q.push(v); ++res; while (!q.empty()) { c = q.front(); q.pop(); for (int i = 0; i < (int) g[c].size(); ++i) { n = g[c][i]; if (!disc[n] && deg[n] == NO_ANS) { deg[n] = v; q.push(n); ++res; } } } return res; } int main() { ios_base::sync_with_stdio(0); vertex_id v; vertex_id e; int deg_tres; cin >> v >> e >> deg_tres; graph_t g(v); vector<int> deg(v, 0); vector<bool> disc(v, 0); int a, b; for (int i = 0; i < e; ++i) { cin >> a >> b; --a; --b; g[a].push_back(b); g[b].push_back(a); ++deg[a]; ++deg[b]; } for (int i = 0; i < v; ++i) { if (!disc[i] && (int) g[i].size() < deg_tres) { trim(g, disc, deg, i, deg_tres); } } for (int i = 0; i < v; ++i) { deg[i] = NO_ANS; } int best_tag = NO_ANS; int best_size = -1; int cur_size; for (int i = 0; i < v; ++i) { if (!disc[i] && deg[i] == NO_ANS) { cur_size = gsize(g, disc, deg, i); if (best_size < cur_size) { best_size = cur_size; best_tag = i; } } } if (best_tag == NO_ANS) { cout << "NIE" << endl; } else { cout << best_size << endl; for (int i = 0; i < v; ++i) { if (deg[i] == best_tag) { cout << (i + 1) << " "; } } cout << endl; } return 0; } |