#include <cstdio> #include <cstring> #include <vector> #include <stack> unsigned find(unsigned * zbiory, unsigned id) { unsigned res = id; while (zbiory[res] != res) res = zbiory[res]; // kompresja sciezki unsigned akt = id; while (zbiory[akt] != res) { unsigned temp = zbiory[akt]; zbiory[akt] = res; akt = temp; } return res; } void unionn(unsigned * zbiory, unsigned * waga, unsigned id1, unsigned id2) { if (waga[id1] > waga[id2]) zbiory[id2] = id1; else if (waga[id1] < waga[id2]) zbiory[id1] = id2; else { zbiory[id2] = id1; waga[id1]++; } } int main(void) { unsigned n,m,d; scanf("%u %u %u", &n, &m, &d); unsigned * nTab = new unsigned[n+1]; memset(nTab, 0, (n+1)*sizeof(unsigned)); unsigned *part1 = new unsigned[m+1]; unsigned *part2 = new unsigned[m+1]; for (unsigned i=0; i<m; i++) { scanf("%u %u", (part1+i), (part2+i)); nTab[part1[i]]++; nTab[part2[i]]++; } std::vector<unsigned> * neight = new std::vector<unsigned>[n+1]; for (unsigned i=1; i<=n; i++) neight[i].reserve(nTab[i]); for (unsigned i=0; i<m; i++) { neight[part1[i]].push_back(part2[i]); neight[part2[i]].push_back(part1[i]); } bool * uzyteczne = new bool[n+1]; memset(uzyteczne, true, (n+1)*sizeof(bool)); std::stack<unsigned> stos; for (unsigned i=1; i<=n; i++) { if ((nTab[i] < d) && uzyteczne[i]) { stos.push(i); uzyteczne[i] = false; } while (!stos.empty()) { unsigned id = stos.top(); stos.pop(); for (auto it = neight[id].begin(); it != neight[id].end(); it++) { nTab[*it]--; if ((nTab[*it] < d) && uzyteczne[*it]) { stos.push(*it); uzyteczne[*it] = false; } } } } unsigned * zbiory = new unsigned[n+1]; unsigned * wagi = new unsigned[n+1]; memset(wagi, 0, (n+1)*sizeof(unsigned)); for (unsigned i=0; i<=n; i++) zbiory[i] = i; for (unsigned i=0; i<m; i++) { if (uzyteczne[part1[i]] && uzyteczne[part2[i]]) { unsigned ojciec1 = find(zbiory, part1[i]); unsigned ojciec2 = find(zbiory, part2[i]); if (ojciec1 != ojciec2) unionn(zbiory, wagi, ojciec1, ojciec2); } } memset(wagi, 0, (n+1)*sizeof(unsigned)); for (unsigned i=1; i<=n; i++) wagi[find(zbiory, i)]++; int maxId = 0; unsigned max = 0; for (unsigned i=1; i<=n; i++) { if (wagi[i] > max) { max = wagi[i]; maxId = i; } } if (max < d) printf("NIE"); else { printf("%u\n", max); for (unsigned i=1; i<=n; i++) { if (find(zbiory,i) == maxId) printf("%u ", i); } } 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 121 122 123 124 125 | #include <cstdio> #include <cstring> #include <vector> #include <stack> unsigned find(unsigned * zbiory, unsigned id) { unsigned res = id; while (zbiory[res] != res) res = zbiory[res]; // kompresja sciezki unsigned akt = id; while (zbiory[akt] != res) { unsigned temp = zbiory[akt]; zbiory[akt] = res; akt = temp; } return res; } void unionn(unsigned * zbiory, unsigned * waga, unsigned id1, unsigned id2) { if (waga[id1] > waga[id2]) zbiory[id2] = id1; else if (waga[id1] < waga[id2]) zbiory[id1] = id2; else { zbiory[id2] = id1; waga[id1]++; } } int main(void) { unsigned n,m,d; scanf("%u %u %u", &n, &m, &d); unsigned * nTab = new unsigned[n+1]; memset(nTab, 0, (n+1)*sizeof(unsigned)); unsigned *part1 = new unsigned[m+1]; unsigned *part2 = new unsigned[m+1]; for (unsigned i=0; i<m; i++) { scanf("%u %u", (part1+i), (part2+i)); nTab[part1[i]]++; nTab[part2[i]]++; } std::vector<unsigned> * neight = new std::vector<unsigned>[n+1]; for (unsigned i=1; i<=n; i++) neight[i].reserve(nTab[i]); for (unsigned i=0; i<m; i++) { neight[part1[i]].push_back(part2[i]); neight[part2[i]].push_back(part1[i]); } bool * uzyteczne = new bool[n+1]; memset(uzyteczne, true, (n+1)*sizeof(bool)); std::stack<unsigned> stos; for (unsigned i=1; i<=n; i++) { if ((nTab[i] < d) && uzyteczne[i]) { stos.push(i); uzyteczne[i] = false; } while (!stos.empty()) { unsigned id = stos.top(); stos.pop(); for (auto it = neight[id].begin(); it != neight[id].end(); it++) { nTab[*it]--; if ((nTab[*it] < d) && uzyteczne[*it]) { stos.push(*it); uzyteczne[*it] = false; } } } } unsigned * zbiory = new unsigned[n+1]; unsigned * wagi = new unsigned[n+1]; memset(wagi, 0, (n+1)*sizeof(unsigned)); for (unsigned i=0; i<=n; i++) zbiory[i] = i; for (unsigned i=0; i<m; i++) { if (uzyteczne[part1[i]] && uzyteczne[part2[i]]) { unsigned ojciec1 = find(zbiory, part1[i]); unsigned ojciec2 = find(zbiory, part2[i]); if (ojciec1 != ojciec2) unionn(zbiory, wagi, ojciec1, ojciec2); } } memset(wagi, 0, (n+1)*sizeof(unsigned)); for (unsigned i=1; i<=n; i++) wagi[find(zbiory, i)]++; int maxId = 0; unsigned max = 0; for (unsigned i=1; i<=n; i++) { if (wagi[i] > max) { max = wagi[i]; maxId = i; } } if (max < d) printf("NIE"); else { printf("%u\n", max); for (unsigned i=1; i<=n; i++) { if (find(zbiory,i) == maxId) printf("%u ", i); } } return 0; } |