#include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <vector> using namespace std; #define MAXN 200001 set<int> E[MAXN]; int rootOf[MAXN]; vector<int> group[MAXN]; struct CmpCities { bool operator () (int c1, int c2) const { auto c1ESize = E[c1].size(); auto c2ESize = E[c2].size(); return c1ESize == c2ESize ? c1 < c2 : c1ESize < c2ESize; } }; int main() { int n, m; auto d = 0u; scanf("%d%d%u", &n, &m, &d); for(int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); E[a].insert(b); E[b].insert(a); } set<int, CmpCities> cities; for(int i = 1; i <= n; ++i) cities.insert(i); decltype(cities.begin()) toRem; int toRemI; while(!cities.empty() && E[toRemI = *(toRem = cities.begin())].size() < d) { cities.erase(toRem); while(!E[toRemI].empty()) { auto first = E[toRemI].begin(); auto adjCityI = *first; E[toRemI].erase(first); cities.erase(adjCityI); E[adjCityI].erase(toRemI); cities.insert(adjCityI); } } vector<int> roots; while(!cities.empty()) { auto root = *cities.begin(); if(rootOf[root] == 0) { roots.push_back(root); rootOf[root] = root; auto& Q = group[root]; Q.push_back(root); auto i = 0u; while(i < Q.size()) { auto city = Q[i++]; cities.erase(cities.find(city)); for(auto adj : E[city]) if(rootOf[adj] == 0) { rootOf[adj] = root; Q.push_back(adj); } } } } if(roots.empty()) { puts("NIE"); } else { auto resultRoot = 0; for(auto root : roots) if(group[root].size() > group[resultRoot].size()) resultRoot = root; auto& resultGroup = group[resultRoot]; sort(resultGroup.begin(), resultGroup.end()); printf("%u\n", resultGroup.size()); for(auto city : resultGroup) printf("%d ", city); } 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 | #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <vector> using namespace std; #define MAXN 200001 set<int> E[MAXN]; int rootOf[MAXN]; vector<int> group[MAXN]; struct CmpCities { bool operator () (int c1, int c2) const { auto c1ESize = E[c1].size(); auto c2ESize = E[c2].size(); return c1ESize == c2ESize ? c1 < c2 : c1ESize < c2ESize; } }; int main() { int n, m; auto d = 0u; scanf("%d%d%u", &n, &m, &d); for(int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); E[a].insert(b); E[b].insert(a); } set<int, CmpCities> cities; for(int i = 1; i <= n; ++i) cities.insert(i); decltype(cities.begin()) toRem; int toRemI; while(!cities.empty() && E[toRemI = *(toRem = cities.begin())].size() < d) { cities.erase(toRem); while(!E[toRemI].empty()) { auto first = E[toRemI].begin(); auto adjCityI = *first; E[toRemI].erase(first); cities.erase(adjCityI); E[adjCityI].erase(toRemI); cities.insert(adjCityI); } } vector<int> roots; while(!cities.empty()) { auto root = *cities.begin(); if(rootOf[root] == 0) { roots.push_back(root); rootOf[root] = root; auto& Q = group[root]; Q.push_back(root); auto i = 0u; while(i < Q.size()) { auto city = Q[i++]; cities.erase(cities.find(city)); for(auto adj : E[city]) if(rootOf[adj] == 0) { rootOf[adj] = root; Q.push_back(adj); } } } } if(roots.empty()) { puts("NIE"); } else { auto resultRoot = 0; for(auto root : roots) if(group[root].size() > group[resultRoot].size()) resultRoot = root; auto& resultGroup = group[resultRoot]; sort(resultGroup.begin(), resultGroup.end()); printf("%u\n", resultGroup.size()); for(auto city : resultGroup) printf("%d ", city); } return 0; } |