#include <iostream> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; int Szukaj(vector< vector<int> >& G, int a, int b) { int p = 0, k = G[a].size() - 1, s; while (p <= k) { s = (p + k) / 2; if (G[a][s] == b) return s; if (G[a][s] < b) p = s + 1; else k = s - 1; } } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin >> n >> m >> d; vector< vector<int> > G(n); int a, b; for (int i = 0; i < m; ++i) { cin >> a >> b; --a; --b; G[a].push_back(b); G[b].push_back(a); } for (int i = 0; i < n; ++i) if (G[i].size() != 0) sort(G[i].begin(), G[i].end()); stack<int> S; vector<bool> odw(n, false); int akt; vector<int> st(n); for (int i = 0; i < n; ++i) st[i] = G[i].size(); vector< vector<bool> > kraw(n); for (int i = 0; i < n; ++i) for (int j = 0; j < G[i].size(); ++j) kraw[i].push_back(true); vector<int> nast(n, 0); vector<bool> wie(n, true); vector<int> odp; for (int i = 0; i < n; ++i) { if (!odw[i]) { akt = i; odw[akt] = true; S.push(akt); vector<int> spojna; spojna.push_back(akt); queue<int> Q; if (st[akt] < d) { Q.push(akt); wie[akt] = false; } while (!S.empty()) { akt = S.top(); S.pop(); for (int j = 0; j < G[akt].size(); ++j) { if (!odw[G[akt][j]]) { odw[G[akt][j]] = true; S.push(G[akt][j]); spojna.push_back(G[akt][j]); if (st[G[akt][j]] < d) { Q.push(G[akt][j]); wie[G[akt][j]] = false; } } } } while (!Q.empty()) { akt = Q.front(); Q.pop(); while (nast[akt] != G[akt].size()) { int kol = G[akt][nast[akt]]; --st[akt]; --st[kol]; if (st[kol] < d) { Q.push(kol); wie[kol] = false; } kraw[akt][nast[akt]] = false; while (nast[akt] < G[akt].size() && !kraw[akt][nast[akt]]) ++nast[akt]; int odwr = Szukaj(G, kol, akt); kraw[kol][odwr] = false; while (nast[kol] < G[kol].size() && !kraw[kol][nast[kol]]) ++nast[kol]; } } vector<bool> odw2(n, false); vector<int> cze; for (int j = 0; j < spojna.size(); ++j) { if (!odw2[spojna[j]] && wie[spojna[j]]) { akt = spojna[j]; odw2[akt] = true; S.push(akt); while (!S.empty()) { akt = S.top(); S.pop(); cze.push_back(akt); for (int k = 0; k < G[akt].size(); ++k) { if (!odw2[G[akt][k]] && wie[G[akt][k]] && kraw[akt][k]) { odw2[G[akt][k]] = true; S.push(G[akt][k]); } } } if (cze.size() > odp.size()) { odp.clear(); for (int k = 0; k < cze.size(); ++k) odp.push_back(cze[k]); } cze.clear(); } } } } if (odp.size() != 0) { cout << odp.size() << endl; sort(odp.begin(), odp.end()); for (int i = 0; i < odp.size(); ++i) cout << odp[i] + 1 << " "; } else cout << "NIE"; 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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | #include <iostream> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; int Szukaj(vector< vector<int> >& G, int a, int b) { int p = 0, k = G[a].size() - 1, s; while (p <= k) { s = (p + k) / 2; if (G[a][s] == b) return s; if (G[a][s] < b) p = s + 1; else k = s - 1; } } int main() { ios_base::sync_with_stdio(0); int n, m, d; cin >> n >> m >> d; vector< vector<int> > G(n); int a, b; for (int i = 0; i < m; ++i) { cin >> a >> b; --a; --b; G[a].push_back(b); G[b].push_back(a); } for (int i = 0; i < n; ++i) if (G[i].size() != 0) sort(G[i].begin(), G[i].end()); stack<int> S; vector<bool> odw(n, false); int akt; vector<int> st(n); for (int i = 0; i < n; ++i) st[i] = G[i].size(); vector< vector<bool> > kraw(n); for (int i = 0; i < n; ++i) for (int j = 0; j < G[i].size(); ++j) kraw[i].push_back(true); vector<int> nast(n, 0); vector<bool> wie(n, true); vector<int> odp; for (int i = 0; i < n; ++i) { if (!odw[i]) { akt = i; odw[akt] = true; S.push(akt); vector<int> spojna; spojna.push_back(akt); queue<int> Q; if (st[akt] < d) { Q.push(akt); wie[akt] = false; } while (!S.empty()) { akt = S.top(); S.pop(); for (int j = 0; j < G[akt].size(); ++j) { if (!odw[G[akt][j]]) { odw[G[akt][j]] = true; S.push(G[akt][j]); spojna.push_back(G[akt][j]); if (st[G[akt][j]] < d) { Q.push(G[akt][j]); wie[G[akt][j]] = false; } } } } while (!Q.empty()) { akt = Q.front(); Q.pop(); while (nast[akt] != G[akt].size()) { int kol = G[akt][nast[akt]]; --st[akt]; --st[kol]; if (st[kol] < d) { Q.push(kol); wie[kol] = false; } kraw[akt][nast[akt]] = false; while (nast[akt] < G[akt].size() && !kraw[akt][nast[akt]]) ++nast[akt]; int odwr = Szukaj(G, kol, akt); kraw[kol][odwr] = false; while (nast[kol] < G[kol].size() && !kraw[kol][nast[kol]]) ++nast[kol]; } } vector<bool> odw2(n, false); vector<int> cze; for (int j = 0; j < spojna.size(); ++j) { if (!odw2[spojna[j]] && wie[spojna[j]]) { akt = spojna[j]; odw2[akt] = true; S.push(akt); while (!S.empty()) { akt = S.top(); S.pop(); cze.push_back(akt); for (int k = 0; k < G[akt].size(); ++k) { if (!odw2[G[akt][k]] && wie[G[akt][k]] && kraw[akt][k]) { odw2[G[akt][k]] = true; S.push(G[akt][k]); } } } if (cze.size() > odp.size()) { odp.clear(); for (int k = 0; k < cze.size(); ++k) odp.push_back(cze[k]); } cze.clear(); } } } } if (odp.size() != 0) { cout << odp.size() << endl; sort(odp.begin(), odp.end()); for (int i = 0; i < odp.size(); ++i) cout << odp[i] + 1 << " "; } else cout << "NIE"; return 0; } |