#include #include #include #include #include #include using namespace std; void wyczyscTabeleTymczasowa(uint32_t* tabela, uint32_t iloscElementow) { for (uint32_t i = 0; i < iloscElementow; ++i) tabela[i] = 0; } int main() { uint32_t iloscWezlow, iloscKrawedziWezla, wezel, wezelSasiedni, idSilnieSkladowej; uint32_t wezelNalezacyDoSilnieSkladowejOMaksymalnejIlosciSasiednichSilnieSkladowych, i; uint32_t maksymalnaIloscSasiednichSilnieSkladowych; vector* listaSasiadowGraf; vector* listaSasiadowGrafTransponowany; list kolejnoscOdwiedzaniaDFSemGraf; stack wezlyDoOdwiedzenia; unordered_set listaIdSasiednichSilnieSkladowychBezPowtorzen; uint32_t* idSilnieSkladowejWezla; uint32_t* odwiedzoneWezly; cin >> iloscWezlow; // inicjujemy tablice listaSasiadowGraf = new vector[iloscWezlow]; listaSasiadowGrafTransponowany = new vector[iloscWezlow]; odwiedzoneWezly = new uint32_t[iloscWezlow]; idSilnieSkladowejWezla = new uint32_t[iloscWezlow]; // ladujemy krawedzie do grafu i grafu transponowanego for (wezel = 0; wezel < iloscWezlow; ++wezel) { cin >> iloscKrawedziWezla; for (i = 0; i < iloscKrawedziWezla; ++i) { cin >> wezelSasiedni; wezelSasiedni--; // tablice w C++ sa od 0, a nie 1, wiec trzeba zmniejszyc ID wezla listaSasiadowGraf[wezel].push_back(wezelSasiedni); listaSasiadowGrafTransponowany[wezelSasiedni].push_back(wezel); } } wyczyscTabeleTymczasowa(odwiedzoneWezly, iloscWezlow); // przegladamy wezly grafu DFSem // zapisujemy czas przetworzenia (kolejnosc odwiedzania post order - dodajemy do listy jak sie 'cofamy') for(uint32_t wezelStartowy = 0; wezelStartowy < iloscWezlow; ++wezelStartowy) { if(odwiedzoneWezly[wezelStartowy]) continue; wezlyDoOdwiedzenia.push(wezelStartowy); while(!wezlyDoOdwiedzenia.empty()) { wezel = wezlyDoOdwiedzenia.top(); wezlyDoOdwiedzenia.pop(); if(odwiedzoneWezly[wezel]) { if(odwiedzoneWezly[wezel] == 1) { kolejnoscOdwiedzaniaDFSemGraf.push_front(wezel); odwiedzoneWezly[wezel] = 2; } continue; } odwiedzoneWezly[wezel] = 1; wezlyDoOdwiedzenia.push(wezel); for(uint32_t wezelSasiedni : listaSasiadowGraf[wezel]) { if(!odwiedzoneWezly[wezelSasiedni]) wezlyDoOdwiedzenia.push(wezelSasiedni); } } } wyczyscTabeleTymczasowa(odwiedzoneWezly, iloscWezlow); // przegladamy wezly grafu transponowanego od najwiekszego czasu przetworzenia // wszystkie przejrzane w ten sposob wezly naleza do jednej silnie spójnej składowej // do tablicy 'idSilnieSkladowejWezla' zapisujemy jaki węzeł nalezy do jakiej skladowej idSilnieSkladowej = 0; for(uint32_t wezelStartowy : kolejnoscOdwiedzaniaDFSemGraf) { if(odwiedzoneWezly[wezelStartowy]) continue; wezlyDoOdwiedzenia.push(wezelStartowy); while(!wezlyDoOdwiedzenia.empty()) { wezel = wezlyDoOdwiedzenia.top(); wezlyDoOdwiedzenia.pop(); if(odwiedzoneWezly[wezel]) { if(odwiedzoneWezly[wezel] == 1) { idSilnieSkladowejWezla[wezel] = idSilnieSkladowej; odwiedzoneWezly[wezel] = 2; } continue; } odwiedzoneWezly[wezel] = 1; wezlyDoOdwiedzenia.push(wezel); for(uint32_t wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) { if(!odwiedzoneWezly[wezelSasiedni]) wezlyDoOdwiedzenia.push(wezelSasiedni); } } idSilnieSkladowej++; } wyczyscTabeleTymczasowa(odwiedzoneWezly, iloscWezlow); // szukamy silnie skladowej o maksymalnej ilosci sasiednich silnie skladowych // w tym przypadku rozpatrujemy te wezly ktore sa SASIADAMI // czyli jest krawedz z X do Y !LUB! z Y do X // w tym celu wystarczy przejsc po liscie sasiadow w grafie i w grafie transponowanym maksymalnaIloscSasiednichSilnieSkladowych = 0; wezelNalezacyDoSilnieSkladowejOMaksymalnejIlosciSasiednichSilnieSkladowych = 0; for(uint32_t wezelStartowy : kolejnoscOdwiedzaniaDFSemGraf) { if(odwiedzoneWezly[wezelStartowy]) continue; wezlyDoOdwiedzenia.push(wezelStartowy); while(!wezlyDoOdwiedzenia.empty()) { wezel = wezlyDoOdwiedzenia.top(); wezlyDoOdwiedzenia.pop(); if(odwiedzoneWezly[wezel]) { if(odwiedzoneWezly[wezel] == 1) { for(uint32_t wezelSasiedni : listaSasiadowGraf[wezel]) { if (idSilnieSkladowejWezla[wezelSasiedni] != idSilnieSkladowejWezla[wezel]) listaIdSasiednichSilnieSkladowychBezPowtorzen.insert(idSilnieSkladowejWezla[wezelSasiedni]); } for(uint32_t wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) { if (idSilnieSkladowejWezla[wezelSasiedni] != idSilnieSkladowejWezla[wezel]) listaIdSasiednichSilnieSkladowychBezPowtorzen.insert(idSilnieSkladowejWezla[wezelSasiedni]); } odwiedzoneWezly[wezel] = 2; } continue; } odwiedzoneWezly[wezel] = 1; wezlyDoOdwiedzenia.push(wezel); for(uint32_t wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) { if(!odwiedzoneWezly[wezelSasiedni]) wezlyDoOdwiedzenia.push(wezelSasiedni); } } if (listaIdSasiednichSilnieSkladowychBezPowtorzen.size() > maksymalnaIloscSasiednichSilnieSkladowych) { maksymalnaIloscSasiednichSilnieSkladowych = listaIdSasiednichSilnieSkladowychBezPowtorzen.size(); wezelNalezacyDoSilnieSkladowejOMaksymalnejIlosciSasiednichSilnieSkladowych = wezel; } listaIdSasiednichSilnieSkladowychBezPowtorzen.clear(); } // jesli najwiecej to 0 sasiadow to ustawiamy, ze najwiecej jest w dowolnym wezle, np. 0 if (maksymalnaIloscSasiednichSilnieSkladowych == 0) wezelNalezacyDoSilnieSkladowejOMaksymalnejIlosciSasiednichSilnieSkladowych = 0; wyczyscTabeleTymczasowa(odwiedzoneWezly, iloscWezlow); // wyswietlenie silnie skladowej o najwiekszej ilosci sasiednich silnie skladowych wezlyDoOdwiedzenia.push(wezelNalezacyDoSilnieSkladowejOMaksymalnejIlosciSasiednichSilnieSkladowych); while(!wezlyDoOdwiedzenia.empty()) { wezel = wezlyDoOdwiedzenia.top(); wezlyDoOdwiedzenia.pop(); if(odwiedzoneWezly[wezel]) { if(odwiedzoneWezly[wezel] == 1) { cout << (wezel + 1) << endl; odwiedzoneWezly[wezel] = 2; } continue; } odwiedzoneWezly[wezel] = 1; wezlyDoOdwiedzenia.push(wezel); for(uint32_t wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) { if(!odwiedzoneWezly[wezelSasiedni] && idSilnieSkladowejWezla[wezelSasiedni] == idSilnieSkladowejWezla[wezel]) wezlyDoOdwiedzenia.push(wezelSasiedni); } } return 0; }