Introducción a algoritmos sobre árboles

Recursos

Video de YouTube (_HECF0Zfe94)

Los árboles (trees) son un tipo particular de grafo que se trata de forma muy distinta a los grafos generales. Estas son algunas propiedades y definiciones de los árboles:

• Un grafo es un árbol sii es conexo y tiene $N$ nodos y $N-1$ aristas
• Un grafo es un árbol sii cada par de nodos tiene exactamente un camino simple entre ellos
• Un grafo es un árbol sii es conexo y no contiene ciclos

Terminología general de árboles:

• Una hoja (leaf) de un árbol es cualquier nodo del árbol con grado $1$
  • Si el árbol está enraizado, la raíz con un único hijo no se considera típicamente una hoja, pero según el problema esto no siempre es así
• Un grafo estrella (star graph) tiene dos definiciones habituales. Conviene entender qué significan: suelen aparecer en subtareas.
  • Definición 1: Solo un nodo tiene grado mayor que $1$
  • Definición 2: Solo un nodo tiene grado mayor que $2$
• Un bosque (forest) es un grafo tal que cada componente conexa es un árbol

Terminología de árboles enraizados:

• Una raíz (root) de un árbol es cualquier nodo del árbol que se considera que está en la «cima»
• El padre (parent) de un nodo $n$ es el primer nodo a lo largo del camino de $n$ a la raíz
  • La raíz no tiene padre. En código esto suele hacerse asignando el padre de la raíz a $-1$.
• Los ancestros de un nodo son su padre y los ancestros del padre
  • Típicamente, un nodo también se considera ancestro de sí mismo (como en la definición de subárbol)
• El subárbol (subtree) de un nodo $n$ es el conjunto de nodos que tienen a $n$ como ancestro
  • Un nodo se considera típicamente parte de su propio subárbol
  • Nota: Esto se confunde fácilmente con subgrafo
• La profundidad, o nivel, de un nodo es su distancia a la raíz

Orden de recorrido del árbol

Cuando ejecutamos DFS sobre un árbol enraizado, el orden en que procesamos cada nodo puede importar. Hay tres órdenes de recorrido habituales:

• Preorden (preorder): Procesar el nodo actual antes de visitar recursivamente a sus hijos. En un árbol binario, esto significa procesar el nodo actual, luego el hijo izquierdo y luego el hijo derecho.
• Inorden (inorder): Visitar recursivamente el hijo izquierdo, procesar el nodo actual y luego visitar recursivamente el hijo derecho. Este orden se usa principalmente en árboles binarios.
• Postorden (postorder): Visitar recursivamente todos los hijos antes de procesar el nodo actual.

Ejemplo - Subordinates

Explicación

En este problema nos dan el padre de cada nodo de un árbol enraizado y queremos calcular el tamaño del subárbol de cada nodo. Un subárbol está compuesto por un nodo raíz y los subárboles de los hijos de esa raíz. Así, el tamaño de un subárbol es uno más el tamaño de los subárboles de los hijos de la raíz.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <bits/stdc++.h>
using namespace std;
 
const int SZ = 2e5;
 
vector<int> children[SZ];
int subtree_size[SZ], depth[SZ];
 
void dfs_size(int node) {
	subtree_size[node] = 1;  // representa la raíz del subárbol de `node`
	// (que sería el propio `node`)
	for (int child : children[node]) {
		depth[child] = depth[node] + 1;  // no hace falta para este problema
		dfs_size(child);
		subtree_size[node] += subtree_size[child];
		// sumamos los subárboles de los hijos de `node` al tamaño del de `node`
	}
}
 
int main() {
	int N;
	cin >> N;
	for (int i = 1; i < N; i++) {
		int parent;
		cin >> parent;
		parent--;
		// este nodo es el padre del nodo i ... también notamos
		// el decremento para dejar el nodo indexado desde 0
		children[parent].push_back(i);
	}
	dfs_size(0);
	for (int i = 0; i < N; i++) {
		cout << subtree_size[i] - 1;
		if (i != N - 1) cout << " ";
	}
	cout << "\n";
}

import java.io.*;
import java.util.*;
 
public class Subordinates {
	static InputReader in = new InputReader(System.in);
	static PrintWriter out = new PrintWriter(System.out);
 
	public static final int MN = 200020;
 
	static int N, M, ans;
	static int[] hd = new int[MN], nx = new int[MN], to = new int[MN], s = new int[MN],
	             p = new int[MN];
 
	public static void adde(int u, int v, int id) {
		nx[id] = hd[u];
		hd[u] = id;
		to[id] = v;
	}
	public static void dfs(int node) {
		s[node] = 1;
		for (int id = hd[node]; id != 0; id = nx[id]) {
			dfs(to[id]);
			s[node] += s[to[id]];
		}
	}
	public static void main(String... args) {
		N = in.nextInt();
		for (int i = 2; i <= N; ++i) {
			p[i] = in.nextInt();
			adde(p[i], i, i);
		}
		dfs(1);
		for (int i = 1; i <= N; ++i) {
			out.print(s[i] - 1);
			if (i < N) out.print(" ");
			else out.println();
		}
		out.close();
	}
}

import sys
 
sys.setrecursionlimit(200006)  # fijamos el límite de recursión
 
 
def dfs(x):  # x es el nodo actual
	ans = 0  # cantidad de subordinados
	for e in edges[x]:
		if e != fa[x - 1]:
			ans += dfs(e)
	sub[x - 1] = ans  # indexar desde 0 es más cómodo para imprimir
	return ans + 1  # sumamos el propio nodo x
 
 
N = int(input())
edges = [[] for _ in range(N + 1)]  # lista de adyacencia vacía
sub = [0 for _ in range(N)]  # cantidad de subordinados
fa = [1] + list(
	map(int, input().split())
)  # padre de cada nodo; el padre del nodo 1 es él mismo
for ind, f in enumerate(fa):
	edges[f].append(ind + 1)  # agregamos aristas a la lista de adyacencia
dfs(1)
for i in sub:
	print(i, end=" ")

Problemas

Quiz