Componentes Conexas

¿Qué es una componente conexa?

Una componente conexa es un grupo máximo de nodos donde puedes llegar de cualquiera a cualquier otro siguiendo aristas.

Analogía: Piensa en islas. Cada isla es una componente conexa: puedes caminar entre cualquier par de puntos dentro de la misma isla, pero no puedes caminar de una isla a otra.

Componente 1:    Componente 2:    Componente 3:
   1 - 2            5                7 - 8
   |   |            |
   3 - 4            6

Este grafo tiene 3 componentes conexas.

Encontrar componentes con DFS

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

const int MAXN = 100005;
vector<int> adj[MAXN];
int comp[MAXN];  // comp[i] = número de componente del nodo i
bool vis[MAXN];

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

    for (int v : adj[u]) {
        if (!vis[v]) {
            dfs(v, id);
        }
    }
}

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);
        adj[v].push_back(u);
    }

    int numComponentes = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            numComponentes++;
            dfs(i, numComponentes);
        }
    }

    cout << "Componentes: " << numComponentes << endl;

    // Imprimir la componente de cada nodo
    for (int i = 1; i <= n; i++) {
        cout << "Nodo " << i << " → Componente " << comp[i] << endl;
    }

    return 0;
}

Encontrar componentes con BFS

void bfs(int inicio, int id) {
    queue<int> q;
    q.push(inicio);
    vis[inicio] = true;
    comp[inicio] = id;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                comp[v] = id;
                q.push(v);
            }
        }
    }
}

Tamaño de cada componente

vector<int> tamComp;

int dfsContar(int u) {
    vis[u] = true;
    int tam = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            tam += dfsContar(v);
        }
    }
    return tam;
}

// En main:
for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
        tamComp.push_back(dfsContar(i));
    }
}

Union-Find (Disjoint Set Union)

Estructura eficiente para manejar componentes de forma dinámica (agregar aristas una por una).

int padre[MAXN], rango[MAXN];

void inicializar(int n) {
    for (int i = 1; i <= n; i++) {
        padre[i] = i;
        rango[i] = 0;
    }
}

int encontrar(int x) {
    if (padre[x] != x) {
        padre[x] = encontrar(padre[x]);  // Compresión de caminos
    }
    return padre[x];
}

bool unir(int a, int b) {
    a = encontrar(a);
    b = encontrar(b);
    if (a == b) return false;  // Ya están en la misma componente

    // Unión por rango
    if (rango[a] < rango[b]) swap(a, b);
    padre[b] = a;
    if (rango[a] == rango[b]) rango[a]++;

    return true;
}

bool mismaComponente(int a, int b) {
    return encontrar(a) == encontrar(b);
}

Complejidad: Casi $O(1)$ por operación (amortizado $O(\alpha(n))$ donde $\alpha$ es la inversa de Ackermann, prácticamente constante).

Ejemplo de uso

int main() {
    int n, m;
    cin >> n >> m;

    inicializar(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        unir(u, v);
    }

    // Contar componentes
    set<int> componentes;
    for (int i = 1; i <= n; i++) {
        componentes.insert(encontrar(i));
    }

    cout << "Componentes: " << componentes.size() << endl;
}

¿DFS/BFS o Union-Find?

Ejercicio de práctica

Dado un grafo con N nodos y M aristas, después responde Q consultas: "¿Los nodos A y B están en la misma componente?"

#include <iostream>
using namespace std;

int padre[100005], rango_arr[100005];

int encontrar(int x) {
    if (padre[x] != x) padre[x] = encontrar(padre[x]);
    return padre[x];
}

void unir(int a, int b) {
    a = encontrar(a); b = encontrar(b);
    if (a == b) return;
    if (rango_arr[a] < rango_arr[b]) swap(a, b);
    padre[b] = a;
    if (rango_arr[a] == rango_arr[b]) rango_arr[a]++;
}

int main() {
    int n, m, q;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        padre[i] = i;
        rango_arr[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        unir(u, v);
    }

    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (encontrar(a) == encontrar(b) ? "Sí" : "No") << endl;
    }

    return 0;
}