#include <cstdio> #include <set> #include <algorithm> #include <queue> #ifdef DBG const bool dbg = true; #else const bool dbg = false; #endif const int MAX_N = 200000; using namespace std; struct Miasto { struct MiastoComp { bool operator() (const Miasto * lhs, const Miasto * rhs) const { return lhs->nr < rhs->nr; } }; int nr; bool odwiedzony; set<Miasto*,MiastoComp> sasiedzi; }; int n, m, d; Miasto* bajtocja[MAX_N + 1]; void wypiszMiasto(Miasto * m) { if (!dbg) return; printf("(nr: %d, odwiedzony: %s, sasiedzi: ", m->nr, m->odwiedzony ? "TAK" : "NIE"); for (auto it = m->sasiedzi.begin(); it != m->sasiedzi.end(); it++) printf("%d,", (*it)->nr); printf(")\n"); } void wypiszMiasta() { if (!dbg) return; for (int i = 0; i < n; i++) wypiszMiasto(bajtocja[i]); } int main() { scanf("%d %d %d", &n, &m, &d); //inicjalizacja for (int i = 0; i < n; i++) { bajtocja[i] = new Miasto; bajtocja[i]->nr = i+1; } // wrzucamy krawedzie w obie strony int a, b; for (int i = 0; i < m; i++) { scanf("%d %d", &a, &b); bajtocja[a-1]->sasiedzi.insert(bajtocja[b-1]); bajtocja[b-1]->sasiedzi.insert(bajtocja[a-1]); } wypiszMiasta(); sort(bajtocja, bajtocja + n, [](Miasto* v, Miasto* w) { return v->sasiedzi.size() < w->sasiedzi.size(); }); wypiszMiasta(); for (int i = 0; i < n; i++) { if (bajtocja[i]->sasiedzi.size() < d) { for (auto it = bajtocja[i]->sasiedzi.begin(); it != bajtocja[i]->sasiedzi.end(); it++) (*it)->sasiedzi.erase(bajtocja[i]); bajtocja[i]->odwiedzony = true; } } wypiszMiasta(); set<Miasto*,Miasto::MiastoComp> S; set<Miasto*,Miasto::MiastoComp> tmpS; queue<Miasto*> q; Miasto *tmpM; for (int i = 0; i < n; i++) { tmpM = bajtocja[i]; if (!tmpM->odwiedzony) { if (dbg) printf("if !odwiedzony...\n"); wypiszMiasto(tmpM); tmpM->odwiedzony = true; tmpS.insert(tmpM); q.push(tmpM); wypiszMiasto(tmpM); while (!q.empty()) { tmpM = q.front(); tmpS.insert(tmpM); q.pop(); for (auto it = tmpM->sasiedzi.begin(); it != tmpM->sasiedzi.end(); it++) { if (dbg) printf("sasiedzi...\n"); if (!(*it)->odwiedzony) { (*it)->odwiedzony = true; q.push(*it); } } } if (tmpS.size() > S.size()) S.swap(tmpS); } } wypiszMiasta(); if (S.empty()) { printf("NIE\n"); return 0; } printf("%lu\n", S.size()); for (auto it = S.begin(); it != S.end(); it++) printf("%d ", (*it)->nr); printf("\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 121 122 | #include <cstdio> #include <set> #include <algorithm> #include <queue> #ifdef DBG const bool dbg = true; #else const bool dbg = false; #endif const int MAX_N = 200000; using namespace std; struct Miasto { struct MiastoComp { bool operator() (const Miasto * lhs, const Miasto * rhs) const { return lhs->nr < rhs->nr; } }; int nr; bool odwiedzony; set<Miasto*,MiastoComp> sasiedzi; }; int n, m, d; Miasto* bajtocja[MAX_N + 1]; void wypiszMiasto(Miasto * m) { if (!dbg) return; printf("(nr: %d, odwiedzony: %s, sasiedzi: ", m->nr, m->odwiedzony ? "TAK" : "NIE"); for (auto it = m->sasiedzi.begin(); it != m->sasiedzi.end(); it++) printf("%d,", (*it)->nr); printf(")\n"); } void wypiszMiasta() { if (!dbg) return; for (int i = 0; i < n; i++) wypiszMiasto(bajtocja[i]); } int main() { scanf("%d %d %d", &n, &m, &d); //inicjalizacja for (int i = 0; i < n; i++) { bajtocja[i] = new Miasto; bajtocja[i]->nr = i+1; } // wrzucamy krawedzie w obie strony int a, b; for (int i = 0; i < m; i++) { scanf("%d %d", &a, &b); bajtocja[a-1]->sasiedzi.insert(bajtocja[b-1]); bajtocja[b-1]->sasiedzi.insert(bajtocja[a-1]); } wypiszMiasta(); sort(bajtocja, bajtocja + n, [](Miasto* v, Miasto* w) { return v->sasiedzi.size() < w->sasiedzi.size(); }); wypiszMiasta(); for (int i = 0; i < n; i++) { if (bajtocja[i]->sasiedzi.size() < d) { for (auto it = bajtocja[i]->sasiedzi.begin(); it != bajtocja[i]->sasiedzi.end(); it++) (*it)->sasiedzi.erase(bajtocja[i]); bajtocja[i]->odwiedzony = true; } } wypiszMiasta(); set<Miasto*,Miasto::MiastoComp> S; set<Miasto*,Miasto::MiastoComp> tmpS; queue<Miasto*> q; Miasto *tmpM; for (int i = 0; i < n; i++) { tmpM = bajtocja[i]; if (!tmpM->odwiedzony) { if (dbg) printf("if !odwiedzony...\n"); wypiszMiasto(tmpM); tmpM->odwiedzony = true; tmpS.insert(tmpM); q.push(tmpM); wypiszMiasto(tmpM); while (!q.empty()) { tmpM = q.front(); tmpS.insert(tmpM); q.pop(); for (auto it = tmpM->sasiedzi.begin(); it != tmpM->sasiedzi.end(); it++) { if (dbg) printf("sasiedzi...\n"); if (!(*it)->odwiedzony) { (*it)->odwiedzony = true; q.push(*it); } } } if (tmpS.size() > S.size()) S.swap(tmpS); } } wypiszMiasta(); if (S.empty()) { printf("NIE\n"); return 0; } printf("%lu\n", S.size()); for (auto it = S.begin(); it != S.end(); it++) printf("%d ", (*it)->nr); printf("\n"); return 0; } |