#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector<set<int> > polaczenia; //kazdemu miastu przyporzadkowuje zbior miast polaczonych z nim droga void usun_miasto(int miasto, int d, vector<bool>& do_usuniecia) { if (do_usuniecia[miasto]==false && polaczenia[miasto].size() < (unsigned)d) { do_usuniecia[miasto]=true; for (set<int>::iterator it=polaczenia[miasto].begin(); it!=polaczenia[miasto].end(); ++it) { polaczenia[*it].erase(miasto); usun_miasto(*it, d, do_usuniecia); } polaczenia[miasto].clear(); } } void znajdz_grupe(int miasto, vector<bool>& sprawdzone_miasta, set<int>& grupa) { if (sprawdzone_miasta[miasto] == false) //miasto nie bylo sprawdzone { sprawdzone_miasta[miasto] = true; grupa.insert(miasto); for(set<int>::iterator it=polaczenia[miasto].begin(); it!=polaczenia[miasto].end(); ++it) { znajdz_grupe(*it, sprawdzone_miasta, grupa); } } } int main() { int ile_miast, ile_drog, d, m1, m2; cin>> ile_miast >>ile_drog >>d; polaczenia.resize(ile_miast+1, {}); for (int ii=0; ii<ile_drog; ii++) { cin >>m1 >>m2; polaczenia[m1].insert(m2); polaczenia[m2].insert(m1); } //wstepna eliminacja - usuwanie miast o mniej niz d polaczeniach z innymi: vector<bool> do_usuniecia = vector<bool>(polaczenia.size(), false); for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++) usun_miasto(miasto, d, do_usuniecia); //znalezienie najwiekszej grupy polaczonych ze soba miast: vector<bool> sprawdzone_miasta = vector<bool>(polaczenia.size(), false); set<int> grupa, najw_grupa; for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++) { znajdz_grupe(miasto, sprawdzone_miasta, grupa); if (grupa.size() > najw_grupa.size()) swap(grupa, najw_grupa); grupa.clear(); } // wyswietlenie wynikow: int ile = najw_grupa.size(); if (ile==1) cout<<"NIE"<<endl; else { cout<<ile<<endl; for (auto it = najw_grupa.begin(); it!=najw_grupa.end(); ++it) cout <<*it<<" "; 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 94 | #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector<set<int> > polaczenia; //kazdemu miastu przyporzadkowuje zbior miast polaczonych z nim droga void usun_miasto(int miasto, int d, vector<bool>& do_usuniecia) { if (do_usuniecia[miasto]==false && polaczenia[miasto].size() < (unsigned)d) { do_usuniecia[miasto]=true; for (set<int>::iterator it=polaczenia[miasto].begin(); it!=polaczenia[miasto].end(); ++it) { polaczenia[*it].erase(miasto); usun_miasto(*it, d, do_usuniecia); } polaczenia[miasto].clear(); } } void znajdz_grupe(int miasto, vector<bool>& sprawdzone_miasta, set<int>& grupa) { if (sprawdzone_miasta[miasto] == false) //miasto nie bylo sprawdzone { sprawdzone_miasta[miasto] = true; grupa.insert(miasto); for(set<int>::iterator it=polaczenia[miasto].begin(); it!=polaczenia[miasto].end(); ++it) { znajdz_grupe(*it, sprawdzone_miasta, grupa); } } } int main() { int ile_miast, ile_drog, d, m1, m2; cin>> ile_miast >>ile_drog >>d; polaczenia.resize(ile_miast+1, {}); for (int ii=0; ii<ile_drog; ii++) { cin >>m1 >>m2; polaczenia[m1].insert(m2); polaczenia[m2].insert(m1); } //wstepna eliminacja - usuwanie miast o mniej niz d polaczeniach z innymi: vector<bool> do_usuniecia = vector<bool>(polaczenia.size(), false); for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++) usun_miasto(miasto, d, do_usuniecia); //znalezienie najwiekszej grupy polaczonych ze soba miast: vector<bool> sprawdzone_miasta = vector<bool>(polaczenia.size(), false); set<int> grupa, najw_grupa; for (unsigned int miasto=1; miasto<polaczenia.size(); miasto++) { znajdz_grupe(miasto, sprawdzone_miasta, grupa); if (grupa.size() > najw_grupa.size()) swap(grupa, najw_grupa); grupa.clear(); } // wyswietlenie wynikow: int ile = najw_grupa.size(); if (ile==1) cout<<"NIE"<<endl; else { cout<<ile<<endl; for (auto it = najw_grupa.begin(); it!=najw_grupa.end(); ++it) cout <<*it<<" "; cout<<endl; } return 0; } |