| Fişierul intrare/ieşire: | ctconexe.in, ctconexe.out | Sursă | ad-hoc |
| Autor | Autor necunoscut | Adăugată de |  Tabara Mihai •Tabara |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Componente Tare Conexe
O componenta tare conexa a unui graf orientat este o multime maximala de varfuri, astfel incat, pentru fiecare pereche de varfuri (i, j), putem ajunge din i in j si din j in i. Cu alte cuvinte, intre oricare doua noduri ale unei componente tare conexe exista cel putin un lant.
Cerinta
Se cere sa se determine toate componentele tare conexe ale grafului dat, prin specificarea varfurilor tuturor componentelor.
Date de intrare
Fisierul de intrare ctconexe.in contine pe prima linie numarul de varfuri N si numarul de arce M. Pe urmatoarele M linii, se afla cate doua numere x si y, cu semnificatia ca exista arc de la x la y.
Date de iesire
In fisierul de iesire ctconexe.out se gaseste pe prima linie numarul NR de componente tare conexe. Pe urmatoarele NR linii, se afiseaza formatul urmator: V X1 X2 ... XV unde V reprezinta numarul de varfuri dintr-o componenta tare conexa, iar X1 X2 ... XN reprezinta varfurile care alcatuiesc respectiva componenta. In acest format de iesire, componentele tare conexe vor fi afisate in ordinea crescatoare a varfului de numar minim, iar in aceeasi componenta tare conexa, varfurile sunt afisate de asemenea in ordine crescatoare.
Restrictii
- 1 ≤ N ≤ 50000
- 1 ≤ M ≤ 100000
- Daca exista arc de la varful x la varful y nu inseamna neaparat ca exista arc de la varful y la varful x
- Poate exista arc de la un varf la el insusi
- Pot exista mai multe arce intre doua noduri x si y
Exemplu
| ctconexe.in | ctconexe.out |
|---|---|
| 8 14 1 2 2 5 5 1 2 3 2 6 5 6 3 4 4 3 3 7 4 8 8 8 7 8 6 7 7 6 | 4 3 1 2 5 2 3 4 2 6 7 1 8 |
Indicatii de rezolvare
- O scurta prezentare a acestui subiect gasiti aici
- Algoritmul de aflare a Componentelor Tare-Conexe ale unui graf il gasiti foarte bine explicat si in cartea Introducere in algoritmi, Thomas Cormen, editura Agora, Cluj-Napoca.
- Algoritmul optim de calculare a componentelor tare conexe ale unui graf se realizeaza cu ajutorul a doua cautari in adancime. Se apeleaza o prima parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare varf v. Pe masura ce fiecare varf este terminat, este inserat in capul unei liste simplu inlantuite. Considerand varfurile in ordinea descrescatoare a timpilor de terminare, se apeleaza o noua cautare in adancime in graful transpus. La fiecare astfel de cautare, varfurile fiecarui arbore in padurea de adancime reprezinta o componenta tare conexa. Complexitatea acestui algoritm este O(N+M).
