Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tribes.in, tribes.out | Sursă | Algoritmiada 2017 Runda 2 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tribes
In ce lume mai abstracta poti trai, decat un graf neorientat cu N noduri si M muchii? Din pacate aceasta abstractizare nu te-a scapat de toate problemele lumesti. Locuitorii grafului s-au separat imediat in triburi, fiecare nod din cele N fiind membru al unuia din cele K triburi existente. Locuitorii grafului sunt foarte circumspecti in relatiile cu membri ai altor triburi decat cel din care fac parte acestia. Un fel in care se manifesta aceasta prudenta este faptul ca un locuitor al nodului X care face parte din tribul T se va incumeta sa calatoreasca pana in nodul Y, de-asemenea parte din tribul T, daca si numai daca exista in graf un drum intre X si Y cu proprietatea ca fiecare nod intermediar este fie din tribul T, fie vecin cu cel putin un nod din tribul T. O astfel de ruta este considerata sigura. Spunem ca doua noduri care fac parte din acelasi trib sunt conectate daca exista o ruta singura intre ele. Numim o componenta conexa a tribului T o submultime maximala de noduri care fac parte din tribul T cu proprietatea ca oricare doua noduri din submultime sunt conectate, in sensul proaspat definit.
Se cere ca pentru fiecare trib dintre cele K sa afisati numarul de componente conexe in care este partitionat acesta.
Date de intrare
Fişierul de intrare tribes.in ...
Date de ieşire
În fişierul de ieşire tribes.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| tribes.in | tribes.out |
|---|---|
| 7 6 3 1 2 2 1 1 3 3 1 2 2 3 3 4 3 5 2 6 7 5 | 1 1 2 |
