#include<iostream> #include<list> #include<stack> using namespace std; int main() { int ile_miast, ile_drog, d; int miasto1, miasto2; bool byla_zmiana = false; cin >> ile_miast; cin >> ile_drog; cin >> d; list<int> rozklad_drog[ile_miast + 1]; int ile_drog_tab[ile_miast + 1]; for (int i = 1; i <= ile_miast; i++) ile_drog_tab[i] = 0; for (int i = 1; i <= ile_drog; i++) { cin >> miasto1; cin >> miasto2; ile_drog_tab[miasto1]++; ile_drog_tab[miasto2]++; rozklad_drog[miasto1].push_front(miasto2); rozklad_drog[miasto2].push_front(miasto1); } // for (int i = 1; i <= ile_drog; i++) // for (auto it = rozklad_drog[i].begin(); it != rozklad_drog[i].end(); it++) // cout << "miasto" << i << " = " << *it << endl; do { byla_zmiana = false; for (int i = 1; i <= ile_miast; i++) { if (ile_drog_tab[i] < d && ile_drog_tab[i] > -1) { byla_zmiana = true; ile_drog_tab[i] = -1; for (auto it = rozklad_drog[i].begin(); it!= rozklad_drog[i].end(); it++) { ile_drog_tab[*it]--; } } } } while (byla_zmiana); // for (int i = 1; i <= ile_miast; i++) // cout << "miasto" << i << " = " << ile_drog_tab[i] << endl; int i = 1; list<int> kandydaci[ile_miast]; int ile_kandydatow = 0; int indeks; stack<int> stos; while (i <= ile_miast && ile_drog_tab[i] <= -1) i++; while (i <= ile_miast) { kandydaci[ile_kandydatow].push_front(i); stos.push(i); while(!stos.empty()) { indeks = stos.top(); stos.pop(); ile_drog_tab[indeks] = -1; for(auto it = rozklad_drog[indeks].begin(); it != rozklad_drog[indeks].end(); it++){ if (ile_drog_tab[*it] > -1) { stos.push(*it); ile_drog_tab[*it] = -1; kandydaci[ile_kandydatow].push_front(*it); } } } ile_kandydatow++; while (i <= ile_miast && ile_drog_tab[i] <= -1) i++; } int najlepsi = 0; for (int j = 0; j < ile_miast; j++) { if (kandydaci[j].size() > kandydaci[najlepsi].size()) najlepsi = j; } kandydaci[najlepsi].sort(); if (kandydaci[najlepsi].size() != 0) { cout << kandydaci[najlepsi].size() << endl; unsigned int ktory_obrot = 1; for (auto it = kandydaci[najlepsi].begin(); it != kandydaci[najlepsi].end(); it++) { cout << *it; if (ktory_obrot != kandydaci[najlepsi].size()) cout << " "; } } else cout << "NIE"; cout << endl; 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 | #include<iostream> #include<list> #include<stack> using namespace std; int main() { int ile_miast, ile_drog, d; int miasto1, miasto2; bool byla_zmiana = false; cin >> ile_miast; cin >> ile_drog; cin >> d; list<int> rozklad_drog[ile_miast + 1]; int ile_drog_tab[ile_miast + 1]; for (int i = 1; i <= ile_miast; i++) ile_drog_tab[i] = 0; for (int i = 1; i <= ile_drog; i++) { cin >> miasto1; cin >> miasto2; ile_drog_tab[miasto1]++; ile_drog_tab[miasto2]++; rozklad_drog[miasto1].push_front(miasto2); rozklad_drog[miasto2].push_front(miasto1); } // for (int i = 1; i <= ile_drog; i++) // for (auto it = rozklad_drog[i].begin(); it != rozklad_drog[i].end(); it++) // cout << "miasto" << i << " = " << *it << endl; do { byla_zmiana = false; for (int i = 1; i <= ile_miast; i++) { if (ile_drog_tab[i] < d && ile_drog_tab[i] > -1) { byla_zmiana = true; ile_drog_tab[i] = -1; for (auto it = rozklad_drog[i].begin(); it!= rozklad_drog[i].end(); it++) { ile_drog_tab[*it]--; } } } } while (byla_zmiana); // for (int i = 1; i <= ile_miast; i++) // cout << "miasto" << i << " = " << ile_drog_tab[i] << endl; int i = 1; list<int> kandydaci[ile_miast]; int ile_kandydatow = 0; int indeks; stack<int> stos; while (i <= ile_miast && ile_drog_tab[i] <= -1) i++; while (i <= ile_miast) { kandydaci[ile_kandydatow].push_front(i); stos.push(i); while(!stos.empty()) { indeks = stos.top(); stos.pop(); ile_drog_tab[indeks] = -1; for(auto it = rozklad_drog[indeks].begin(); it != rozklad_drog[indeks].end(); it++){ if (ile_drog_tab[*it] > -1) { stos.push(*it); ile_drog_tab[*it] = -1; kandydaci[ile_kandydatow].push_front(*it); } } } ile_kandydatow++; while (i <= ile_miast && ile_drog_tab[i] <= -1) i++; } int najlepsi = 0; for (int j = 0; j < ile_miast; j++) { if (kandydaci[j].size() > kandydaci[najlepsi].size()) najlepsi = j; } kandydaci[najlepsi].sort(); if (kandydaci[najlepsi].size() != 0) { cout << kandydaci[najlepsi].size() << endl; unsigned int ktory_obrot = 1; for (auto it = kandydaci[najlepsi].begin(); it != kandydaci[najlepsi].end(); it++) { cout << *it; if (ktory_obrot != kandydaci[najlepsi].size()) cout << " "; } } else cout << "NIE"; cout << endl; return 0; } |