Componentes conectados em um grafo

Dado um grafo não direcionado $G$ com $n$ nós e $m$ arestas. Devemos encontrar nele todos os componentes conectados, ou seja, vários grupos de vértices de modo que dentro de um grupo cada vértice possa ser alcançado pelo outro e não exista caminho entre grupos diferentes.

Um algoritmo para resolver o problema

Implementação

int n;
vector<int> g[MAXN] ;
bool used[MAXN] ;
vector<int> comp ;

void dfs(int v) {
    used[v] = true ;
    comp.push_back(v);
    for (size_t i = 0; i < (int) g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to])
            dfs(to);
    }
}

void find_comps() {
    for (int i = 0; i < n ; ++i)
        used [i] = false;
    for (int i = 0; i < n ; ++i)
        if (!used[i]) {
            comp.clear();
            dfs(i);
            cout << "Componente:" ;
            for (size_t j = 0; j < comp.size(); ++j)
                cout << ' ' << comp[j];
            cout << endl ;
        }
}

Problemas