#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; /** * Mateusz Smiech * Zadanie Mistrzostwa [B] z 2. rundy Potyczek * Algorytmicznych 2015. */ int main() { ios_base::sync_with_stdio(0); int n, m, d; //Constants int current, another, i, j, u, v, s; //Temporary variables cin >> n >> m >> d; vector<vector<int> > graph(n); vector<int> degrees(n); for (i = 0; i < n; i++) { vector<int> vect; graph.push_back(vect); degrees[i] = 0; } for (i = 0; i < m; i++) { cin >> u >> v; graph[u - 1].push_back(v - 1); graph[v - 1].push_back(u - 1); degrees[u - 1]++; degrees[v - 1]++; } vector<bool> processed(n); queue<int> q; for (i = 0; i < n; i++) { if (degrees[i] >= d) continue; q.push(i); processed[i] = true; } while (!q.empty()) { current = q.front(); q.pop(); s = graph[current].size(); for (i = 0; i < s; i++) { another = graph[current][i]; degrees[another]--; if (degrees[another] < d && !processed[another]) { q.push(another); processed[another] = true; } } } vector<int> bestVector; int bestScore = 0; for (i = 0; i < n; i++) { int currentScore = 0; vector<int> currentVector; if (processed[i]) continue; q.push(i); processed[i] = true; while (!q.empty()) { current = q.front(); q.pop(); currentScore++; currentVector.push_back(current); s = graph[current].size(); for (j = 0; j < s; j++) { another = graph[current][j]; if (processed[another]) continue; processed[another] = true; q.push(another); } } if (currentScore > bestScore) { bestScore = currentScore; bestVector = currentVector; } } if (bestScore == 0) cout << "NIE" << endl; else { std::sort(bestVector.begin(), bestVector.end()); cout << bestScore << endl; cout << (bestVector[0] + 1); for (i = 1; i < bestVector.size(); i++) cout << " " << (bestVector[i] + 1); 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; /** * Mateusz Smiech * Zadanie Mistrzostwa [B] z 2. rundy Potyczek * Algorytmicznych 2015. */ int main() { ios_base::sync_with_stdio(0); int n, m, d; //Constants int current, another, i, j, u, v, s; //Temporary variables cin >> n >> m >> d; vector<vector<int> > graph(n); vector<int> degrees(n); for (i = 0; i < n; i++) { vector<int> vect; graph.push_back(vect); degrees[i] = 0; } for (i = 0; i < m; i++) { cin >> u >> v; graph[u - 1].push_back(v - 1); graph[v - 1].push_back(u - 1); degrees[u - 1]++; degrees[v - 1]++; } vector<bool> processed(n); queue<int> q; for (i = 0; i < n; i++) { if (degrees[i] >= d) continue; q.push(i); processed[i] = true; } while (!q.empty()) { current = q.front(); q.pop(); s = graph[current].size(); for (i = 0; i < s; i++) { another = graph[current][i]; degrees[another]--; if (degrees[another] < d && !processed[another]) { q.push(another); processed[another] = true; } } } vector<int> bestVector; int bestScore = 0; for (i = 0; i < n; i++) { int currentScore = 0; vector<int> currentVector; if (processed[i]) continue; q.push(i); processed[i] = true; while (!q.empty()) { current = q.front(); q.pop(); currentScore++; currentVector.push_back(current); s = graph[current].size(); for (j = 0; j < s; j++) { another = graph[current][j]; if (processed[another]) continue; processed[another] = true; q.push(another); } } if (currentScore > bestScore) { bestScore = currentScore; bestVector = currentVector; } } if (bestScore == 0) cout << "NIE" << endl; else { std::sort(bestVector.begin(), bestVector.end()); cout << bestScore << endl; cout << (bestVector[0] + 1); for (i = 1; i < bestVector.size(); i++) cout << " " << (bestVector[i] + 1); cout << endl; } return 0; } |