Checando se um grafo é acíclico e encontrando um ciclo em $O(M)$

Considere um grafo direcionado ou não direcionado, sem loops e arestas múltiplas. Temos que verificar se é acíclico e, se não for, encontrar algum ciclo.

Podemos resolver esse problema usando uma DFS em $O(M)$ onde $M$ é o número de arestas.

Algoritmo

Executaremos uma série de DFS's no grafo. Inicialmente todos os vértices são brancos (0). Em cada vértice não visitado (branco) iniciamos a DFS, marcar com cinza (1) enquanto entra no vértice e marcar com preto (2) na saída dele. Se a DFS se mover para um vértice cinza, encontramos um ciclo! (se o grafo não for direcionado, a aresta para o parente não será considerada). O próprio ciclo pode ser reconstruído usando a array de parentes.

Implementação

Aqui está uma implementação para um grafo direcionado.

int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;

bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u))
                return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}

void find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;

    for (int v = 0; v < n; v++) {
        if (color[v] == 0 && dfs(v))
            break;
    }

    if (cycle_start == -1) {
        cout << "Acíclico" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());

        cout << "Ciclo: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}