Detección de Ciclos

Ciclos en grafos no dirigidos

Un ciclo existe si encontramos un vecino ya visitado que no es el padre del nodo actual.

vector<int> adj[MAXN];
bool vis[MAXN];
bool tieneCiclo = false;

void dfs(int u, int padre) {
    vis[u] = true;

    for (int v : adj[u]) {
        if (!vis[v]) {
            dfs(v, u);
        } else if (v != padre) {
            tieneCiclo = true;
        }
    }
}

También puedes usar Union-Find: si al agregar una arista, ambos extremos ya están en la misma componente, hay ciclo.

bool hayCicloUF(int n, vector<pair<int,int>> &aristas) {
    inicializar(n);
    for (auto [u, v] : aristas) {
        if (encontrar(u) == encontrar(v)) return true;
        unir(u, v);
    }
    return false;
}

Ciclos en grafos dirigidos

Usamos la coloración blanco/gris/negro:

int color[MAXN];  // 0=blanco, 1=gris, 2=negro

bool dfsCiclo(int u) {
    color[u] = 1;  // Gris: en proceso

    for (int v : adj[u]) {
        if (color[v] == 1) return true;   // Back edge → ciclo
        if (color[v] == 0 && dfsCiclo(v)) return true;
    }

    color[u] = 2;  // Negro: terminado
    return false;
}

bool hayCicloDirigido(int n) {
    fill(color, color + n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && dfsCiclo(i)) return true;
    }
    return false;
}

Encontrar un ciclo (no solo detectarlo)

int padre_ciclo[MAXN];
int inicio_ciclo = -1, fin_ciclo = -1;

bool dfsBuscarCiclo(int u) {
    color[u] = 1;

    for (int v : adj[u]) {
        if (color[v] == 1) {
            fin_ciclo = u;
            inicio_ciclo = v;
            return true;
        }
        if (color[v] == 0) {
            padre_ciclo[v] = u;
            if (dfsBuscarCiclo(v)) return true;
        }
    }

    color[u] = 2;
    return false;
}

void imprimirCiclo() {
    vector<int> ciclo;
    ciclo.push_back(inicio_ciclo);
    for (int v = fin_ciclo; v != inicio_ciclo; v = padre_ciclo[v]) {
        ciclo.push_back(v);
    }
    ciclo.push_back(inicio_ciclo);
    reverse(ciclo.begin(), ciclo.end());

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

Ejercicio de práctica

Dado un grafo dirigido, imprime "SI" si tiene un ciclo, "NO" si no.

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100005];
int color[100005];

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && dfs(i)) {
            cout << "SI" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}