#ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include <cstdio> #include <set> #include <stack> using namespace std; set<int> routes[200001]; int sizes[200001]; int subset[200001]; int main() { int n, m, d; scanf("%d %d %d\n", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d\n", &a, &b); routes[a].insert(b); routes[b].insert(a); } stack<int> removals; for (int i = 1; i <= n; i++) { if (routes[i].size() < d) { removals.push(i); } sizes[i] = 0; subset[i] = 0; } while (removals.size() > 0) { int source = removals.top(); removals.pop(); for (auto dest = routes[source].begin(); dest != routes[source].end(); dest++) { routes[*dest].erase(source); if (routes[*dest].size() < d) { removals.push(*dest); } } routes[source].clear(); } stack<int> travel; for (int i = 1; i <= n; i++) { if (subset[i] == 0 && routes[i].size() > 0) { subset[i] = i; travel.push(i); while (travel.size() > 0) { int current = travel.top(); travel.pop(); for (auto dest = routes[current].begin(); dest != routes[current].end(); dest++) { if (subset[*dest] == 0) { subset[*dest] = i; travel.push(*dest); } } } } } for (int i = 1; i <= n; i++) { if (subset[i] != 0) { sizes[subset[i]]++; } } int maxsize = 0; int maxsubset = 0; for (int i = 1; i <= n; i++) { if (sizes[i] > maxsize) { maxsize = sizes[i]; maxsubset = i; } } if (maxsize > 0) { printf("%d\n%d", maxsize, maxsubset); for (int i = maxsubset + 1; i <= n; i++) { if (subset[i] == maxsubset) { printf(" %d", i); } } printf("\n"); } 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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include <cstdio> #include <set> #include <stack> using namespace std; set<int> routes[200001]; int sizes[200001]; int subset[200001]; int main() { int n, m, d; scanf("%d %d %d\n", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d\n", &a, &b); routes[a].insert(b); routes[b].insert(a); } stack<int> removals; for (int i = 1; i <= n; i++) { if (routes[i].size() < d) { removals.push(i); } sizes[i] = 0; subset[i] = 0; } while (removals.size() > 0) { int source = removals.top(); removals.pop(); for (auto dest = routes[source].begin(); dest != routes[source].end(); dest++) { routes[*dest].erase(source); if (routes[*dest].size() < d) { removals.push(*dest); } } routes[source].clear(); } stack<int> travel; for (int i = 1; i <= n; i++) { if (subset[i] == 0 && routes[i].size() > 0) { subset[i] = i; travel.push(i); while (travel.size() > 0) { int current = travel.top(); travel.pop(); for (auto dest = routes[current].begin(); dest != routes[current].end(); dest++) { if (subset[*dest] == 0) { subset[*dest] = i; travel.push(*dest); } } } } } for (int i = 1; i <= n; i++) { if (subset[i] != 0) { sizes[subset[i]]++; } } int maxsize = 0; int maxsubset = 0; for (int i = 1; i <= n; i++) { if (sizes[i] > maxsize) { maxsize = sizes[i]; maxsubset = i; } } if (maxsize > 0) { printf("%d\n%d", maxsize, maxsubset); for (int i = maxsubset + 1; i <= n; i++) { if (subset[i] == maxsubset) { printf(" %d", i); } } printf("\n"); } else { printf("NIE\n"); } return 0; } |