#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cassert> using namespace std; class Vertex { public: vector<int> neigh; bool czy; int id; int suma; Vertex () { czy = true; suma = 0; } Vertex(int i){ id = i; czy = true; suma = 0; } }; int main(){ int n, n2, m, d; cin >> n; cin >> m; cin >> d; n2 = n; Vertex tab[n]; for (int i = 0; i < n; i ++) tab[i] = Vertex(i+1); for (int i = 0; i < m; i++){ int a, b; cin >> a; cin >> b; tab[a-1].neigh.push_back(b); tab[a-1].suma ++; tab[b-1].neigh.push_back(a); tab[b-1].suma ++; } vector<int> queue; for (int i = 0; i < n; i++) { //cout << i << endl; if (!tab[i].czy) continue; if (tab[i].suma < d) { //cout << "---" << i+1 << endl; tab[i].czy = false; n2--; //cout << i+1 << "out\n"; queue.push_back(i+1); while (!queue.empty()) { int v = queue.back(); //cout << "queue -> " << v << endl; queue.pop_back(); Vertex vert = tab[v-1]; for (int j = 0; j < vert.neigh.size(); j++){ Vertex* v2 = &tab[vert.neigh[j]-1]; //cout << "testing " << v2->id << "\n"; assert(v2->id == vert.neigh[j]); if (!v2->czy) continue; //cout << "still testing " << v2->id << "\n"; v2->suma --; if (v2->suma == d-1) { v2->czy = false; n2 --; //cout << v2->id << "out1\n"; queue.push_back(v2->id); } } //cout << tab[0].czy << " " << tab[1].czy << " " << tab[2].czy << endl; } } } if (n2 != 0) { cout << n2 << endl; for (int i = 0; i< n; i++){ if (tab[i].czy) { cout << i+1 << " "; } } cout << endl; } else { cout << "NIE\n"; } }
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 | #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cassert> using namespace std; class Vertex { public: vector<int> neigh; bool czy; int id; int suma; Vertex () { czy = true; suma = 0; } Vertex(int i){ id = i; czy = true; suma = 0; } }; int main(){ int n, n2, m, d; cin >> n; cin >> m; cin >> d; n2 = n; Vertex tab[n]; for (int i = 0; i < n; i ++) tab[i] = Vertex(i+1); for (int i = 0; i < m; i++){ int a, b; cin >> a; cin >> b; tab[a-1].neigh.push_back(b); tab[a-1].suma ++; tab[b-1].neigh.push_back(a); tab[b-1].suma ++; } vector<int> queue; for (int i = 0; i < n; i++) { //cout << i << endl; if (!tab[i].czy) continue; if (tab[i].suma < d) { //cout << "---" << i+1 << endl; tab[i].czy = false; n2--; //cout << i+1 << "out\n"; queue.push_back(i+1); while (!queue.empty()) { int v = queue.back(); //cout << "queue -> " << v << endl; queue.pop_back(); Vertex vert = tab[v-1]; for (int j = 0; j < vert.neigh.size(); j++){ Vertex* v2 = &tab[vert.neigh[j]-1]; //cout << "testing " << v2->id << "\n"; assert(v2->id == vert.neigh[j]); if (!v2->czy) continue; //cout << "still testing " << v2->id << "\n"; v2->suma --; if (v2->suma == d-1) { v2->czy = false; n2 --; //cout << v2->id << "out1\n"; queue.push_back(v2->id); } } //cout << tab[0].czy << " " << tab[1].czy << " " << tab[2].czy << endl; } } } if (n2 != 0) { cout << n2 << endl; for (int i = 0; i< n; i++){ if (tab[i].czy) { cout << i+1 << " "; } } cout << endl; } else { cout << "NIE\n"; } } |