#include <iostream> #include <vector> #include <unordered_set> #include <set> using namespace std; int main() { std::ios_base::sync_with_stdio (false); // cin.tie(NULL); int n, m, d; cin >> n; cin >> m; cin >> d; vector<unordered_set<int> > g(n+1); unordered_set<int> vg; int s, e; for (int i = 0; i < m; ++i) { cin >> s; cin >> e; vg.insert(s); vg.insert(e); //cout << "inserting " << s << " " << e << endl; g[s].insert(e); if (s != e) g[e].insert(s); } // clear the data bool bad_found = true; unordered_set<int> cands; for (auto itvg = vg.begin(); itvg != vg.end(); ++itvg) { int i = *itvg; if (g[i].size() < d) cands.insert(i); } while (cands.size() > 0) { int i = *(cands.begin()); cands.erase(cands.begin()); unordered_set<int>::iterator it; for (it = g[i].begin(); it != g[i].end(); ++it) { g[*it].erase(i); if (g[*it].size() < d) cands.insert(*it); } } //cout << endl; for (int i = 1; i < n+1; ++i) { // cout << g[i].size() << endl; } unordered_set<int> g2; for (int i = 1; i < n+1; ++i) { if (g[i].size() >= d) g2.insert(i); } vector<set<int> > sfor; if (g2.size() == 0) { cout << "NIE" << endl; return 0; } while (g2.size() > 0) { set<int> dfset; int st = *(g2.begin()); // cout << "dfs start " << st << endl; vector<int> S; S.push_back(st); while (S.size() > 0) { int v = S.back(); S.pop_back(); if (g2.find(v) != g2.end()) { g2.erase(v); dfset.insert(v); for (unordered_set<int>::iterator it = g[v].begin(); it != g[v].end(); ++it) { S.push_back(*it); } } } sfor.push_back(dfset); } int maxsfor = -1; int msforpos = 0; //cout << "debug sfor size " << sfor.size() << endl; for (int i = 0; i < sfor.size(); ++i) { // cout << "sfor[i].size() " << sfor[i].size() << endl; int sforsize = sfor[i].size(); if (sforsize > maxsfor) { // cout << "max1 " << maxsfor << endl; maxsfor = sforsize; // cout << "max2 " << maxsfor << endl; msforpos = i; } else { // cout << "yyy? " << sfor[i].size() << " maxsfor " << maxsfor << " bool ? " << (sfor[i].size() > maxsfor) << " uu ? " << (3 > -1) << endl; } } cout << maxsfor << endl; int zz = 0; for (auto it = sfor[msforpos].begin(); it != sfor[msforpos].end(); ++it) { ++zz; cout << *it; if (zz < maxsfor) cout << " "; } 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 | #include <iostream> #include <vector> #include <unordered_set> #include <set> using namespace std; int main() { std::ios_base::sync_with_stdio (false); // cin.tie(NULL); int n, m, d; cin >> n; cin >> m; cin >> d; vector<unordered_set<int> > g(n+1); unordered_set<int> vg; int s, e; for (int i = 0; i < m; ++i) { cin >> s; cin >> e; vg.insert(s); vg.insert(e); //cout << "inserting " << s << " " << e << endl; g[s].insert(e); if (s != e) g[e].insert(s); } // clear the data bool bad_found = true; unordered_set<int> cands; for (auto itvg = vg.begin(); itvg != vg.end(); ++itvg) { int i = *itvg; if (g[i].size() < d) cands.insert(i); } while (cands.size() > 0) { int i = *(cands.begin()); cands.erase(cands.begin()); unordered_set<int>::iterator it; for (it = g[i].begin(); it != g[i].end(); ++it) { g[*it].erase(i); if (g[*it].size() < d) cands.insert(*it); } } //cout << endl; for (int i = 1; i < n+1; ++i) { // cout << g[i].size() << endl; } unordered_set<int> g2; for (int i = 1; i < n+1; ++i) { if (g[i].size() >= d) g2.insert(i); } vector<set<int> > sfor; if (g2.size() == 0) { cout << "NIE" << endl; return 0; } while (g2.size() > 0) { set<int> dfset; int st = *(g2.begin()); // cout << "dfs start " << st << endl; vector<int> S; S.push_back(st); while (S.size() > 0) { int v = S.back(); S.pop_back(); if (g2.find(v) != g2.end()) { g2.erase(v); dfset.insert(v); for (unordered_set<int>::iterator it = g[v].begin(); it != g[v].end(); ++it) { S.push_back(*it); } } } sfor.push_back(dfset); } int maxsfor = -1; int msforpos = 0; //cout << "debug sfor size " << sfor.size() << endl; for (int i = 0; i < sfor.size(); ++i) { // cout << "sfor[i].size() " << sfor[i].size() << endl; int sforsize = sfor[i].size(); if (sforsize > maxsfor) { // cout << "max1 " << maxsfor << endl; maxsfor = sforsize; // cout << "max2 " << maxsfor << endl; msforpos = i; } else { // cout << "yyy? " << sfor[i].size() << " maxsfor " << maxsfor << " bool ? " << (sfor[i].size() > maxsfor) << " uu ? " << (3 > -1) << endl; } } cout << maxsfor << endl; int zz = 0; for (auto it = sfor[msforpos].begin(); it != sfor[msforpos].end(); ++it) { ++zz; cout << *it; if (zz < maxsfor) cout << " "; } cout << endl; return 0; } |