Conteo de inversiones, componentes conexas y profundidad acumulada en árboles binarios de búsqueda en C++

Programas en C++ de algoritmos y estructuras de datos

A continuación se presentan tres programas en C++ que resuelven problemas clásicos de algoritmia: el conteo de inversiones mediante una variante de merge sort, el conteo de componentes conexas en una imagen mediante DFS, y el cálculo de la profundidad acumulada al insertar elementos en un árbol binario de búsqueda.

1. Conteo de inversiones con merge sort

El siguiente código cuenta el número de inversiones de un arreglo, es decir, pares de índices i < j tales que a[i] > a[j]. Utiliza la técnica de divide y vencerás durante la fase de mezcla.

#include <bits/stdc++.h>
using namespace std;

long long merge_count(vector<long long>& a, int l, int r) {
    if (r - l <= 1) return 0;
    int m = (l + r) / 2;
    long long inv = merge_count(a, l, m) + merge_count(a, m, r);
    vector<long long> tmp;
    int i = l, j = m;
    while (i < m && j < r)
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else tmp.push_back(a[j++]), inv += m - i;
    while (i < m) tmp.push_back(a[i++]);
    while (j < r) tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + l);
    return inv;
}

int main() {
    int n;
    while (cin >> n && n) {
        vector<long long> a(n);
        for (auto &x : a) cin >> x;
        cout << merge_count(a, 0, n) << '\n';
    }
}

La complejidad temporal es O(n log n), ya que cada nivel de recursión realiza una mezcla lineal.

2. Conteo de componentes conexas en una imagen

Este programa recibe una imagen formada por caracteres - y cuenta las regiones conexas mediante una búsqueda en profundidad (DFS) que marca las celdas visitadas con #.

#include <bits/stdc++.h>
using namespace std;

int filas, columnas;
vector<string> imagen;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= filas || y >= columnas || imagen[x][y] != '-') return;
    imagen[x][y] = '#';
    for (int k = 0; k < 4; k++) dfs(x + dx[k], y + dy[k]);
}

int main() {
    int caso = 1;
    while (cin >> filas >> columnas) {
        imagen.resize(filas);
        for (int i = 0; i < filas; i++) cin >> imagen[i];
        int estrellas = 0;
        for (int i = 0; i < filas; i++)
            for (int j = 0; j < columnas; j++)
                if (imagen[i][j] == '-') {
                    estrellas++;
                    dfs(i, j);
                }
        cout << "Case " << caso++ << ": " << estrellas << "\n";
    }
    return 0;
}

Cada celda se visita como máximo una vez, por lo que la complejidad es O(filas × columnas) por caso de prueba.

3. Profundidad acumulada en un árbol binario de búsqueda

El último programa inserta valores en un árbol binario de búsqueda (BST) y, tras cada inserción, imprime la suma acumulada de las profundidades en las que se ha colocado cada nuevo nodo. La raíz tiene profundidad 0.

#include <bits/stdc++.h>
using namespace std;

struct Nodo {
    int valor;
    Nodo *izq, *der;
    Nodo(int v): valor(v), izq(NULL), der(NULL) {}
};

int insertar(Nodo *&raiz, int x, int prof=0) {
    if (!raiz) {
        raiz = new Nodo(x);
        return prof;
    }
    if (x < raiz->valor) return insertar(raiz->izq, x, prof+1);
    else return insertar(raiz->der, x, prof+1);
}

int main() {
    int n, x; cin >> n;
    Nodo *raiz = NULL;
    long long suma = 0;
    while (n--) {
        cin >> x;
        suma += insertar(raiz, x);
        cout << suma << "\n";
    }
}

En el peor caso (árbol degenerado), cada inserción cuesta O(n), mientras que en un árbol balanceado el coste es O(log n).