o ile dobrze rozumiem (nieskierowany?), to w zasadzie, nieinteresuje Cie jak ten graf wyglada, ale jakie numery wierzcholkow wchodza w sklad ktorej skladowej spojnosci.
trzymajac wierzcholki w mapie/tablicy numerskladowej -> posortowana lista wierzcholkow, jestes w stanie sprawdzic czy pojedynczy wierzcholek nalezy do jakiejs skladowej po prostu przez przeszukanie binarne owych list
algo:
zaczynasz z pusta mapa list
w petli:
wczytujesz "krawedz"
szukasz w mapie wierzcholka pierwszego -> numerskladowej1
szukasz w mapie wierzcholka drugiego -> numerskladowej2
jesli:
- udalo sie znalezc i pierwszy i drugi wierzcholek, to nalezy scalic te skladowe w jedna
- jeden z nich nalezal do jakiejs skladowej, drugi do zadnej -- ten nienalezacy nalezy dodac do owej skladowej
- jesli zaden nie nalezal - nalezy dodac nowa skladowa zawierajaca te dwa wierzcholki
po przetworzeniu wszystkich krawedzi, w mapie zostana rozdzielone skladowe
to tyle slowem lopatologii.
mozna to zrobic szybciej: trzymaj dwie mapy/tablice:
a) wierzcholek->numerskladowej
b) numerskladowej->listawierzcholkow
pierwszej uzywaj do sprawdzania kto do czego nalezy, drugiej - do scalania skladowych. oczywiscie obie musza byc pilnie synchronizowane.