#include <algorithm> #include <iostream> #include <list> #include <stack> #include <vector> #include <utility> using namespace std; typedef pair<bool, vector<int> > vertex; void dfs_visit(vector<vertex>& g, vertex u, vector<int>& neigh_num, int d) { vertex v; u.first = true; for (int i = 0; i != u.second.size(); i++) { neigh_num[u.second[i]-1]--; v = g[u.second[i]-1]; if (!v.first && neigh_num[u.second[i]-1] < d) dfs_visit(g, v, neigh_num, d); } } void dfs_d_deg_vertices(vector<vertex>& g, vector<int>& neigh_num, int d) { for (int i = 0; i < g.size(); i++) if (!g[i].first && g[i].second.size() < d) dfs_visit(g, g[i], neigh_num, d); } pair<int, vector<int> > dfs_largest_connected_component(vector<vertex> g, vector<int> neigh_num, int d) { stack<vertex, list<vertex> > s; int max_cc, act_cc; vertex u, v; vector<int> max_cc_vert; pair<int, vector<int> > ret; max_cc = 0; for (int i = 0; i < g.size(); i++) if (!g[i].first && g[i].second.size() >= d) { vector<int> act_cc_vert; act_cc = 1; act_cc_vert.push_back(i+1); g[i].first = true; s.push(g[i]); while (!s.empty()) { cout << endl; u = s.top(); s.pop(); for (int j = 0; j < u.second.size(); j++) { if (!(g[u.second[j]-1].first) && neigh_num[u.second[j]-1] >= d) { g[u.second[j]-1].first = true; s.push(g[u.second[j]-1]); act_cc++; act_cc_vert.push_back(u.second[j]); } } } if (act_cc > max_cc) { max_cc = act_cc; max_cc_vert = act_cc_vert; } } ret.first = max_cc; ret.second = max_cc_vert; return ret; } int main() { int n, m, d, temp1, temp2; pair<int, int> ind_neighbours; vector<vertex> graph; vector<int> neighbours_num; pair<int, vector<int> > ret; cin >> n >> m >> d; if (d > 1000) { cout << "NIE" << endl; return 0; } if (d * (d+1) > 2 * m) { cout << "NIE" << endl; return 0; } graph.resize(n); neighbours_num.resize(n); for (int i = 0; i != m; i++) { cin >> temp1 >> temp2; graph[temp1-1].second.push_back(temp2); graph[temp2-1].second.push_back(temp1); } for (int i = 0; i != n; i++) neighbours_num[i] = graph[i].second.size(); dfs_d_deg_vertices(graph, neighbours_num, d); for (int i = 0; i != n; i++) graph[i].first = false; ret = dfs_largest_connected_component(graph, neighbours_num, d); sort(ret.second.begin(), ret.second.end()); if (ret.first < d + 1) cout << "NIE" << endl; else { cout << ret.first << endl; cout << ret.second[0]; for (int i = 1; i != ret.second.size(); i++) cout << " " << ret.second[i]; 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 | #include <algorithm> #include <iostream> #include <list> #include <stack> #include <vector> #include <utility> using namespace std; typedef pair<bool, vector<int> > vertex; void dfs_visit(vector<vertex>& g, vertex u, vector<int>& neigh_num, int d) { vertex v; u.first = true; for (int i = 0; i != u.second.size(); i++) { neigh_num[u.second[i]-1]--; v = g[u.second[i]-1]; if (!v.first && neigh_num[u.second[i]-1] < d) dfs_visit(g, v, neigh_num, d); } } void dfs_d_deg_vertices(vector<vertex>& g, vector<int>& neigh_num, int d) { for (int i = 0; i < g.size(); i++) if (!g[i].first && g[i].second.size() < d) dfs_visit(g, g[i], neigh_num, d); } pair<int, vector<int> > dfs_largest_connected_component(vector<vertex> g, vector<int> neigh_num, int d) { stack<vertex, list<vertex> > s; int max_cc, act_cc; vertex u, v; vector<int> max_cc_vert; pair<int, vector<int> > ret; max_cc = 0; for (int i = 0; i < g.size(); i++) if (!g[i].first && g[i].second.size() >= d) { vector<int> act_cc_vert; act_cc = 1; act_cc_vert.push_back(i+1); g[i].first = true; s.push(g[i]); while (!s.empty()) { cout << endl; u = s.top(); s.pop(); for (int j = 0; j < u.second.size(); j++) { if (!(g[u.second[j]-1].first) && neigh_num[u.second[j]-1] >= d) { g[u.second[j]-1].first = true; s.push(g[u.second[j]-1]); act_cc++; act_cc_vert.push_back(u.second[j]); } } } if (act_cc > max_cc) { max_cc = act_cc; max_cc_vert = act_cc_vert; } } ret.first = max_cc; ret.second = max_cc_vert; return ret; } int main() { int n, m, d, temp1, temp2; pair<int, int> ind_neighbours; vector<vertex> graph; vector<int> neighbours_num; pair<int, vector<int> > ret; cin >> n >> m >> d; if (d > 1000) { cout << "NIE" << endl; return 0; } if (d * (d+1) > 2 * m) { cout << "NIE" << endl; return 0; } graph.resize(n); neighbours_num.resize(n); for (int i = 0; i != m; i++) { cin >> temp1 >> temp2; graph[temp1-1].second.push_back(temp2); graph[temp2-1].second.push_back(temp1); } for (int i = 0; i != n; i++) neighbours_num[i] = graph[i].second.size(); dfs_d_deg_vertices(graph, neighbours_num, d); for (int i = 0; i != n; i++) graph[i].first = false; ret = dfs_largest_connected_component(graph, neighbours_num, d); sort(ret.second.begin(), ret.second.end()); if (ret.first < d + 1) cout << "NIE" << endl; else { cout << ret.first << endl; cout << ret.second[0]; for (int i = 1; i != ret.second.size(); i++) cout << " " << ret.second[i]; cout << endl; } return 0; } |