/* * Mistrzostwa.cpp * * Created on: 29 wrz 2015 * Author: Marcin Skibinski */ #include <cstdio> #include <vector> #include <set> #include <stack> #include <algorithm> std::vector<int> makeCitySet(std::vector<std::set<int>> & cities, std::vector<bool> & visited, int start) { std::vector<int> result; std::stack<int> toVisit; result.push_back(start); visited[start] = true; toVisit.push(start); while (!toVisit.empty()) { auto cityNumber = toVisit.top(); toVisit.pop(); for (auto & city : cities[cityNumber]) { if (!visited[city]) { visited[city] = true; result.push_back(city); toVisit.push(city); } } } return result; } int main() { int n, m, d; int a, b; std::scanf("%d %d %d", &n, &m, &d); std::vector<std::set<int>> cities(n+1); std::vector<bool> visited(n+1); std::stack<int> toRemove; for (int i=0; i<m; ++i) { std::scanf("%d %d", &a, &b); cities[a].insert(b); cities[b].insert(a); } for (int i=1; i<=n; ++i) { if (cities[i].size() < d) { toRemove.push(i); } } while (!toRemove.empty()) { auto cityNumber = toRemove.top(); toRemove.pop(); for (auto & city : cities[cityNumber]) { cities[city].erase(cityNumber); if (cities[city].size() + 1 == d) { toRemove.push(city); } } cities[cityNumber].clear(); } std::vector<int> result; for (int i=1; i<=n; ++i) { if (!cities[i].empty()) { auto tmpResult = makeCitySet(cities, visited, i); if (tmpResult.size() > result.size()) { result = tmpResult; } } } if (result.empty()) { std::printf("NIE\n"); } else { std::sort(result.begin(), result.end()); printf("%d\n", result.size()); for (auto city : result) { printf("%d ", city); } printf("\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 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 | /* * Mistrzostwa.cpp * * Created on: 29 wrz 2015 * Author: Marcin Skibinski */ #include <cstdio> #include <vector> #include <set> #include <stack> #include <algorithm> std::vector<int> makeCitySet(std::vector<std::set<int>> & cities, std::vector<bool> & visited, int start) { std::vector<int> result; std::stack<int> toVisit; result.push_back(start); visited[start] = true; toVisit.push(start); while (!toVisit.empty()) { auto cityNumber = toVisit.top(); toVisit.pop(); for (auto & city : cities[cityNumber]) { if (!visited[city]) { visited[city] = true; result.push_back(city); toVisit.push(city); } } } return result; } int main() { int n, m, d; int a, b; std::scanf("%d %d %d", &n, &m, &d); std::vector<std::set<int>> cities(n+1); std::vector<bool> visited(n+1); std::stack<int> toRemove; for (int i=0; i<m; ++i) { std::scanf("%d %d", &a, &b); cities[a].insert(b); cities[b].insert(a); } for (int i=1; i<=n; ++i) { if (cities[i].size() < d) { toRemove.push(i); } } while (!toRemove.empty()) { auto cityNumber = toRemove.top(); toRemove.pop(); for (auto & city : cities[cityNumber]) { cities[city].erase(cityNumber); if (cities[city].size() + 1 == d) { toRemove.push(city); } } cities[cityNumber].clear(); } std::vector<int> result; for (int i=1; i<=n; ++i) { if (!cities[i].empty()) { auto tmpResult = makeCitySet(cities, visited, i); if (tmpResult.size() > result.size()) { result = tmpResult; } } } if (result.empty()) { std::printf("NIE\n"); } else { std::sort(result.begin(), result.end()); printf("%d\n", result.size()); for (auto city : result) { printf("%d ", city); } printf("\n"); } } |