Prosto jest obliczyć komponenty grafu w czasie liniowym (w odniesieniu do liczby wierzchołków i krawędzi grafu), używając albo wyszukiwania pierwszego rzędu (breadth-first search), albo pierwszego rzędu (depth-first search). W obu przypadkach wyszukiwanie, które rozpoczyna się od określonego wierzchołka v, znajdzie przed powrotem cały składnik zawierający v (i nie więcej). Aby znaleźć wszystkie składowe grafu, należy wykonać pętlę przez jego wierzchołki, rozpoczynając nowe wyszukiwanie typu breadth first lub depth first za każdym razem, gdy pętla dotrze do wierzchołka, który nie został jeszcze włączony do poprzednio znalezionej składowej. Hopcroft & Tarjan (1973) opisuje zasadniczo ten algorytm i stwierdza, że w tym momencie był on „dobrze znany”.
Istnieją również wydajne algorytmy dynamicznego śledzenia składowych grafu w miarę dodawania wierzchołków i krawędzi, jako proste zastosowanie struktur danych disjoint-set. Algorytmy te wymagają zamortyzowanego czasu O(α(n)) na operację, gdzie dodawanie wierzchołków i krawędzi oraz określanie składowej, w której dany wierzchołek się znajduje, to obie operacje, a α(n) jest bardzo wolno rosnącą odwrotnością bardzo szybko rosnącej funkcji Ackermanna. Powiązanym problemem jest śledzenie składowych w miarę usuwania wszystkich krawędzi z grafu, jedna po drugiej; istnieje algorytm rozwiązujący ten problem ze stałym czasem na zapytanie i O(|V||E|) czasem na utrzymanie struktury danych; jest to amortyzowany koszt O(|V|) na usunięcie krawędzi. Dla lasów koszt ten może być zredukowany do O(q + |V| log |V|), lub O(log |V|) amortyzowanego kosztu na usunięcie krawędzi (Shiloach & Even 1981).
Badacze badali również algorytmy znajdowania komponentów w bardziej ograniczonych modelach obliczeń, takich jak programy, w których pamięć robocza jest ograniczona do logarytmicznej liczby bitów (zdefiniowanej przez klasę złożoności L). Lewis & Papadimitriou (1982) zapytał, czy możliwe jest sprawdzenie w logprzestrzeni, czy dwa wierzchołki należą do tego samego składnika grafu nieskierowanego, i zdefiniował klasę złożoności SL problemów logprzestrzennie równoważnych łączności. Wreszcie Reingoldowi (2008) udało się znaleźć algorytm rozwiązania tego problemu łączności w przestrzeni logarytmicznej, pokazując, że L = SL.
.