#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector <int> ile_s; struct cmp { bool operator () (const int &a, const int &b) { if (ile_s [a] < ile_s [b]) return true; if (ile_s [b] < ile_s [a]) return false; return a < b; } }; int main() { std::ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; vector < vector <int> > drogi; drogi.resize (n+1); ile_s.resize(n +1, 0); int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; drogi [a].push_back(b); drogi [b].push_back(a); } for (int i = 1; i <= n; i++) ile_s [i] = drogi [i].size(); set <int, cmp> kopiec; for (int i = 1; i <= n; i++) kopiec.insert(i); while(ile_s[*kopiec.begin()] < d && !kopiec.empty()) { int v, u, c; u = *kopiec.begin(); kopiec.erase(kopiec.begin()); for (int i = 0; i < drogi [u].size(); i++) { v = drogi [u] [i]; if (ile_s[v] != 0) { kopiec.erase(kopiec.find(v)); ile_s[v] -= 1; kopiec.insert (v); } } ile_s[u] = 0; } int k = kopiec.size(); vector <int> wyn; while (!kopiec.empty()) { wyn.push_back(*kopiec.begin()); kopiec.erase(kopiec.begin()); } sort (wyn.begin(), wyn.end()); if (k == 0) cout << "NIE"; else { cout << k << endl; for (int i = 0; i < k; i++) cout << wyn [i] << " "; } 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 | #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector <int> ile_s; struct cmp { bool operator () (const int &a, const int &b) { if (ile_s [a] < ile_s [b]) return true; if (ile_s [b] < ile_s [a]) return false; return a < b; } }; int main() { std::ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; vector < vector <int> > drogi; drogi.resize (n+1); ile_s.resize(n +1, 0); int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; drogi [a].push_back(b); drogi [b].push_back(a); } for (int i = 1; i <= n; i++) ile_s [i] = drogi [i].size(); set <int, cmp> kopiec; for (int i = 1; i <= n; i++) kopiec.insert(i); while(ile_s[*kopiec.begin()] < d && !kopiec.empty()) { int v, u, c; u = *kopiec.begin(); kopiec.erase(kopiec.begin()); for (int i = 0; i < drogi [u].size(); i++) { v = drogi [u] [i]; if (ile_s[v] != 0) { kopiec.erase(kopiec.find(v)); ile_s[v] -= 1; kopiec.insert (v); } } ile_s[u] = 0; } int k = kopiec.size(); vector <int> wyn; while (!kopiec.empty()) { wyn.push_back(*kopiec.begin()); kopiec.erase(kopiec.begin()); } sort (wyn.begin(), wyn.end()); if (k == 0) cout << "NIE"; else { cout << k << endl; for (int i = 0; i < k; i++) cout << wyn [i] << " "; } return 0; } |