#include <cstdio> #include <set> #include <vector> using namespace std; vector<set<int> > graph; vector<int> cityGroup; int main() { int n, m, d; int a, b; scanf("%d %d %d", &n, &m, &d); graph.assign(n+1, set<int>()); cityGroup.assign(n+1, 0); for (int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); graph[a].insert(b); graph[b].insert(a); } set<int> toRemove; for (int i = 1; i <= n; ++i) { if (graph[i].size() < d) { if (!graph[i].empty()) { toRemove.insert(i); } cityGroup[i] = -1; } } set<int>::iterator it; int current; while (!toRemove.empty()) { it = toRemove.begin(); current = (*it); toRemove.erase(it); for (it = graph[current].begin(); it != graph[current].end(); ++it) { graph[*it].erase(current); if (cityGroup[*it] != -1) { if (graph[*it].size() < d) { if (!graph[*it].empty()) { toRemove.insert(*it); } cityGroup[*it] = -1; } } } graph[current].erase(graph[current].begin(), graph[current].end()); } vector<int> groupCounts; groupCounts.push_back(0); for (int i = 1; i <= n; ++i) { if (cityGroup[i] == 0) { int groupNumber = groupCounts.size(); int count = 1; set<int> toAdd; cityGroup[i] = groupNumber; toAdd.insert(graph[i].begin(), graph[i].end()); while (!toAdd.empty()) { it = toAdd.begin(); current = (*it); toAdd.erase(it); cityGroup[current] = groupNumber; count++; for (it = graph[current].begin(); it != graph[current].end(); ++it) { if (cityGroup[*it] == 0) { toAdd.insert(*it); } } } groupCounts.push_back(count); } } if (groupCounts.size() > 1) { int best = 0; int bestGroup = 0; for (int i = 1; i < groupCounts.size(); ++i) { if (groupCounts[i] > best) { bestGroup = i; best = groupCounts[i]; } } printf("%d\n", best); for (int i = 1; i <= n; ++i) { if (cityGroup[i] == bestGroup) { printf("%d ", i); } } } else { printf("NIE\n"); } 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 <cstdio> #include <set> #include <vector> using namespace std; vector<set<int> > graph; vector<int> cityGroup; int main() { int n, m, d; int a, b; scanf("%d %d %d", &n, &m, &d); graph.assign(n+1, set<int>()); cityGroup.assign(n+1, 0); for (int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); graph[a].insert(b); graph[b].insert(a); } set<int> toRemove; for (int i = 1; i <= n; ++i) { if (graph[i].size() < d) { if (!graph[i].empty()) { toRemove.insert(i); } cityGroup[i] = -1; } } set<int>::iterator it; int current; while (!toRemove.empty()) { it = toRemove.begin(); current = (*it); toRemove.erase(it); for (it = graph[current].begin(); it != graph[current].end(); ++it) { graph[*it].erase(current); if (cityGroup[*it] != -1) { if (graph[*it].size() < d) { if (!graph[*it].empty()) { toRemove.insert(*it); } cityGroup[*it] = -1; } } } graph[current].erase(graph[current].begin(), graph[current].end()); } vector<int> groupCounts; groupCounts.push_back(0); for (int i = 1; i <= n; ++i) { if (cityGroup[i] == 0) { int groupNumber = groupCounts.size(); int count = 1; set<int> toAdd; cityGroup[i] = groupNumber; toAdd.insert(graph[i].begin(), graph[i].end()); while (!toAdd.empty()) { it = toAdd.begin(); current = (*it); toAdd.erase(it); cityGroup[current] = groupNumber; count++; for (it = graph[current].begin(); it != graph[current].end(); ++it) { if (cityGroup[*it] == 0) { toAdd.insert(*it); } } } groupCounts.push_back(count); } } if (groupCounts.size() > 1) { int best = 0; int bestGroup = 0; for (int i = 1; i < groupCounts.size(); ++i) { if (groupCounts[i] > best) { bestGroup = i; best = groupCounts[i]; } } printf("%d\n", best); for (int i = 1; i <= n; ++i) { if (cityGroup[i] == bestGroup) { printf("%d ", i); } } } else { printf("NIE\n"); } return 0; } |