Компоненте повезаности
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
Напиши програм који одређује компоненте повезаности у неусмереном графу. Компонента повезаности је скуп чворова таквих да из сваког чвора у компоненти постоји пут до сваког другог чвора у компоненти и не постоји пут ни до једног другог чвора ван компоненте.
Улаз
Из прве линије стандардног улаза учитава се број чворова (1≤v≤100) и број грана (0≤e≤v(v−1)2) неусмерног графа. У наредних e линија налази се опис грана (пар чворова, раздвојених размаком, при чему се чворови броје од 0 до v−1).
Излаз
На стандардни излаз за сваки чвор исписати редни број компоненте којој припада (компоненте се броје од 1). Редослед компоненти одређен је редоследном њихових најмањих елемената (нпр. ако чвор 3 и чвор 7 нису у истој компоненти, редни број компоненте која садржи 3 треба да буде мањи од редног броја компоненте која садржи 7).
Пример
Улаз
6 3 1 3 2 4 5 0
Излаз
1 2 3 2 3 1
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.