Componentes fuertemente conexas

Componentes fuertemente conexas (SCC)

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Planets & Kingdoms	Fácil	SCC	Solución

La definición de un reino en este problema es equivalente a la definición de una componente fuertemente conexa. Podemos calcular estas componentes usando el algoritmo de Kosaraju o el de Tarjan, ambos descritos abajo.

Algoritmo de Kosaraju

Recursos
Fuente	Recurso	Notas
CPH	17 - Strong Connectivity
Wikipedia	Kosaraju's Algorithm
TC	Kosaraju's Algorithm for SCCs

Explicación

En la primera fase, el algoritmo realiza una búsqueda en profundidad (DFS) sobre el grafo original para determinar los tiempos de salida de los vértices; es decir, el nodo que se procesa último quedará en la cima de la pila (orden topológico inverso). A medida que cada vértice termina de procesarse, se lo apila. En la fase siguiente, los nodos se procesan desapilándolos en orden de tiempos de finalización decrecientes. Este ordenamiento se usará en la segunda fase.

En la segunda fase, el algoritmo realiza otra DFS, esta vez sobre el grafo transpuesto, donde todas las aristas están invertidas. La DFS procesa los nodos según el orden definido por la pila de la primera fase. Al invertir las aristas y seguir este orden específico, cada ejecución de DFS en esta fase puede identificar todos los vértices de una SCC antes de pasar a la siguiente.

Sabemos que el grafo transpuesto tendrá las mismas componentes fuertemente conexas (SCC) que el original porque invertir una arista no cambia la alcanzabilidad dentro de las componentes. Cada SCC es a la vez maximal y disjunta. Esto significa que dentro de una SCC, todo par de vértices es mutuamente alcanzable: se puede ir de cualquier vértice $u$ a cualquier otro vértice $v$ , y viceversa. El término “maximal” indica que no se pueden agregar más vértices a una SCC sin perder su propiedad de conexión fuerte. Además, las SCC son disjuntas, lo que significa que ningún vértice puede pertenecer a más de una SCC. Si un vértice formara parte de dos SCC, esas SCC se fusionarían en una SCC más grande. Por lo tanto, invertir aristas no afecta las conexiones no dirigidas del grafo original.

Durante la segunda DFS, procesamos los vértices en el orden determinado por la pila de la primera fase. Esto garantiza que empezamos con el vértice que terminó último en la DFS inicial, que está garantizado como parte de una SCC sin aristas salientes hacia otras SCC: esencialmente es un “sumidero ” en el grafo transpuesto.

Al procesar los vértices en este orden específico, exploramos por completo todos los vértices de la SCC actual antes de pasar a la siguiente. Las SCC son subgrafos maximales en los que cada vértice puede alcanzar a todos los demás del mismo subgrafo, así que la DFS recorrerá todos los nodos de una SCC y la aislará por completo. Una vez procesada toda la SCC, pasamos al siguiente vértice de mayor tiempo de salida que aún no se visitó, asegurando que cada SCC se trata de forma independiente y exhaustiva, de modo que ningún vértice de otra SCC se incluya por error en la actual.

Para visualización, consultar el recurso de TopCoder mencionado aquí .

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
 
const int N = 1e5 + 1;
 
// adj_t es el transpuesto de adj
std::vector<int> adj[N], adj_t[N];
std::vector<int> order;
std::vector<int> vis(N), id(N);
 
// calcula el orden en que se procesan los nodos
void dfs1(int v) {
	vis[v] = true;
	for (int u : adj[v]) {
		if (!vis[u]) { dfs1(u); }
	}
	order.push_back(v);
}
 
/*
 * recorre una SCC a la vez y
 * asigna el ID de componente a todos los nodos de una SCC
 */
void dfs2(int x, int comp) {
	vis[x] = true;
 
	for (int u : adj_t[x]) {
		if (!vis[u]) { dfs2(u, comp); }
	}
	id[x] = comp;
}
 
int main() {
	int n, m;
	std::cin >> n >> m;
 
	for (int i = 1; i <= m; i++) {
		int u, v;
		std::cin >> u >> v;
		adj[u].push_back(v);
		adj_t[v].push_back(u);
	}
 
	vis.assign(N, false);
 
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) { dfs1(i); }
	}
 
	vis.assign(N, false);
	std::reverse(begin(order), end(order));
	int comps = 0;
	for (int v : order) {
		if (!vis[v]) {
			comps++;  // contador de SCC
			dfs2(v, comps);
		}
	}
 
	std::cout << comps << '\n';
 
	for (int i = 1; i <= n; i++) { std::cout << id[i] << " \n"[i == n]; }
}


import java.io.*;
import java.util.*;
 
public class Main {
	static final int N = 100001;
	static boolean[] vis = new boolean[N + 1];
	// Lista de adyacencia de vecinos
	static List<Integer>[] adj = new ArrayList[N + 1];
	// adjT es el transpuesto de adj
	static List<Integer>[] adjT = new ArrayList[N + 1];
	static int[] id = new int[N + 1];
	static List<Integer> dfsOrder = new ArrayList<>();
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
		for (int i = 1; i <= n; i++) {
			adj[i] = new ArrayList<>();
			adjT[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int a = io.nextInt();
			int b = io.nextInt();
			adj[a].add(b);
			adjT[b].add(a);
		}
 
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) { dfs(i, 1, i); }
		}
 
		Arrays.fill(vis, false);
		int components = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (!vis[dfsOrder.get(i)]) {
				components++;
				dfs(dfsOrder.get(i), 2, components);
			}
		}
 
		io.println(components);
		for (int i = 1; i <= n; i++) { io.print(id[i] + " "); }
		io.close();
	}
 
	private static void dfs(int x, int pass, int num) {
		vis[x] = true;
		List<Integer> ad = (pass == 1) ? adj[x] : adjT[x];
		for (int e : ad) {
			if (!vis[e]) { dfs(e, pass, num); }
		}
		dfsOrder.add(x);
		if (pass == 2) { id[x] = num; }
	}
 
	// CodeSnip{Kattio}
}


order = []
 
 
def dfs1(v: int):
	"""Calcular el orden de procesamiento de los nodos."""
	stack = [v]
	while stack:
		node = stack[-1]
		if not vis[node]:
			vis[node] = True
		finished = True
		for u in adj[node]:
			if not vis[u]:
				stack.append(u)
				finished = False
				break
		if finished:
			order.append(stack.pop())
		else:
			vis[node] = True
 
 
def dfs2(x: int, comp: int):
	"""Recorrer una SCC y asignar números de componente a cada una."""
	stack = [x]
	while stack:
		node = stack.pop()
		if not vis[node]:
			vis[node] = True
			comp_id[node] = comp
			for u in rev_adj[node]:
				if not vis[u]:
					stack.append(u)
 
 
n, m = map(int, input().split())
 
adj = [[] for _ in range(n)]
rev_adj = [[] for _ in range(n)]
vis = [False] * n
comp_id = [0] * n
 
for _ in range(m):
	u, v = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	rev_adj[v].append(u)
 
for i in range(n):
	if not vis[i]:
		dfs1(i)
 
vis = [False] * n
comps = 0
for i in range(len(order) - 1, -1, -1):
	v = order[i]
	if not vis[v]:
		comps += 1  # contador de SCC
		dfs2(v, comps)
 
print(comps)
print(*comp_id)

Algoritmo de Tarjan

Recursos
Fuente	Recurso	Notas
CPC	7 - Graphs 1
CP2	4.2.9 - Finding SCCs
Wikipedia	Tarjan's SCC Algorithm

Implementación

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

C++


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
/** Recibe una lista de adyacencia y calcula las SCC del grafo. */
class TarjanSolver {
  private:
	vector<vector<int>> rev_adj;
	vector<int> post;
	vector<int> comp;
 
	vector<bool> visited;
	int timer = 0;
	int id = 0;
 
	void fill_post(int at) {
		visited[at] = true;
		for (int n : rev_adj[at]) {
			if (!visited[n]) { fill_post(n); }
		}
		post[at] = timer++;
	}
 
	void find_comp(int at) {
		visited[at] = true;
		comp[at] = id;
		for (int n : adj[at]) {
			if (!visited[n]) { find_comp(n); }
		}
	}
 
  public:
	const vector<vector<int>> &adj;
 
	TarjanSolver(const vector<vector<int>> &adj)
	    : adj(adj), rev_adj(adj.size()), post(adj.size()), comp(adj.size()),
	      visited(adj.size()) {
		vector<int> nodes(adj.size());
		for (int n = 0; n < adj.size(); n++) {
			nodes[n] = n;
			for (int next : adj[n]) { rev_adj[next].push_back(n); }
		}
 
		for (int n = 0; n < adj.size(); n++) {
			if (!visited[n]) { fill_post(n); }
		}
		std::sort(nodes.begin(), nodes.end(),
		          [&](int n1, int n2) { return post[n1] > post[n2]; });
 
		visited.assign(adj.size(), false);
		for (int n : nodes) {
			if (!visited[n]) {
				find_comp(n);
				id++;
			}
		}
	}
 
	int comp_num() const { return id; }
 
	int get_comp(int n) const { return comp[n]; }
};
 
int main() {
	int planet_num;
	int tele_num;
	std::cin >> planet_num >> tele_num;
	vector<vector<int>> adj(planet_num);
	for (int t = 0; t < tele_num; t++) {
		int from, to;
		std::cin >> from >> to;
		adj[--from].push_back(--to);
	}
 
	TarjanSolver scc(adj);
	cout << scc.comp_num() << '\n';
	for (int p = 0; p < planet_num - 1; p++) { cout << scc.get_comp(p) + 1 << ' '; }
	cout << scc.get_comp(planet_num - 1) + 1 << endl;
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Coin Collector	Fácil	SCC, DP	Solución
POI	2018 - Bike Paths	Fácil	SCC, DP	Solución
CF	Ralph and Mushrooms	Normal	SCC, DP	—
Old Gold	Grass Cownoisseur	Normal	SCC	—
CF	Catowice City	Normal	SCC	—
CF	Falling Sand	Difícil	SCC	—
POI	2012 - Festival	Difícil	SCC	Solución
Kattis	Proving Equivalences	Difícil	SCC	Solución
CSES	New Flight Routes	Muy difícil	SCC	Solución

2-SAT

Recursos
Fuente	Recurso	Notas
CF	2-SAT
cp-algo	2-SAT
Algorithms Live!	2SAT

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Giant Pizza	Normal		en el módulo

Explicación

Introducción

El problema de CSES ya nos da una fórmula booleana en forma normal conjuntiva (CNF) que consiste en una serie de cláusulas OR lógicas unidas por AND, de esta forma:

(\lnot x_1 \lor x_2) \land (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor \lnot x_2) \land (x_1 \lor \lnot x_3)

Antes de continuar, intentar relacionar esto con teoría de grafos. Pista: representar una variable y su negación con dos nodos.

Construcción

Como dice la pista, podemos construir un grafo en el que cada variable tiene dos nodos: uno para ella misma y otro para su negación. Vamos a intentar asignar a cada nodo un valor de verdad. Nótese que el valor de uno de los nodos de la variable determina el del otro, ya que si conocemos el valor de un nodo, el otro es la negación de ese valor.

Ahora, para cada cláusula $(a \lor b)$ , agregamos dos aristas dirigidas: $\lnot a \rightarrow b$ y $\lnot b \rightarrow a$ . Esto significa que si $a$ era falsa, entonces $b$ debe ser verdadera, y viceversa.

Con estas aristas, una SCC implica un grupo de valores que todos deben tener el mismo valor de verdad.

Resolver el grafo

La única forma de que haya una asignación imposible de valores de verdad es que un nodo y su negación estén en la misma SCC, ya que esto significa que un booleano y su negación tienen que ser ambos verdaderos, lo cual es imposible.

Si el grafo es consistente y no hay configuraciones imposibles, podemos empezar a asignar valores de verdad, empezando por las SCC que no tienen aristas salientes hacia otras SCC y procediendo hacia atrás. Con las SCC iniciales, las fijamos todas en verdadero. En cuanto a las demás SCC, si un valor ya se asignó porque su negación está en una componente procesada antes, hay que asignar todos los demás valores de la componente a ese valor.

Debido a ciertas propiedades del grafo que construimos , podemos garantizar que la asignación resultante de las variables no tiene SCC “verdaderas” que lleven a SCC “falsas”. Una demostración de esto queda fuera del alcance de este módulo.

Implementación

Usamos el algoritmo de Tarjan porque ya nos da un orden topológico en el que procesar los nodos. Sin embargo, también es posible usar el algoritmo de Kosaraju.

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

C++


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{SCC Solver}
class TarjanSolver {
  private:
	vector<vector<int>> rev_adj;
	vector<int> post;
	vector<int> comp;
 
	vector<bool> visited;
	int timer = 0;
	int id = 0;
 
	void fill_post(int at) {
		visited[at] = true;
		for (int n : rev_adj[at]) {
			if (!visited[n]) { fill_post(n); }
		}
		post[at] = timer++;
	}
 
	void find_comp(int at) {
		visited[at] = true;
		comp[at] = id;
		for (int n : adj[at]) {
			if (!visited[n]) { find_comp(n); }
		}
	}
 
  public:
	const vector<vector<int>> &adj;
	TarjanSolver(const vector<vector<int>> &adj)
	    : adj(adj), rev_adj(adj.size()), post(adj.size()), comp(adj.size()),
	      visited(adj.size()) {
		vector<int> nodes(adj.size());
		for (int n = 0; n < adj.size(); n++) {
			nodes[n] = n;
			for (int next : adj[n]) { rev_adj[next].push_back(n); }
		}
 
		for (int n = 0; n < adj.size(); n++) {
			if (!visited[n]) { fill_post(n); }
		}
		std::sort(nodes.begin(), nodes.end(),
		          [&](int n1, int n2) { return post[n1] > post[n2]; });
 
		visited.assign(adj.size(), false);
		for (int n : nodes) {
			if (!visited[n]) {
				find_comp(n);
				id++;
			}
		}
	}
 
	int comp_num() const { return id; }
 
	int get_comp(int n) const { return comp[n]; }
};
// EndCodeSnip
 
struct Clause {
	int var1;   // id de la primera variable
	bool neg1;  // ¿está negada?
	int var2;
	bool neg2;
};
 
/**
 * @return a vector of booleans that satisfy the given clauses,
 * or an empty vector if no such set of booleans exist
 */
vector<int> solve_sat(const vector<Clause> &clauses, int var_num) {
	vector<vector<int>> adj(2 * var_num);
	// 2 * var es la variable, y 2 * var + 1 es su negación
	for (const Clause &c : clauses) {
		// la falsedad de la primera implica la verdad de la segunda
		adj[2 * c.var1 + !c.neg1].push_back(2 * c.var2 + c.neg2);
		// y viceversa
		adj[2 * c.var2 + !c.neg2].push_back(2 * c.var1 + c.neg1);
	}
 
	TarjanSolver scc(adj);
	// lista de todas las componentes del grafo
	vector<vector<int>> comps(scc.comp_num());
	for (int i = 0; i < 2 * var_num; i += 2) {
		// ¿un nodo y su negación comparten la misma componente?
		if (scc.get_comp(i) == scc.get_comp(i + 1)) { return {}; }
		comps[scc.get_comp(i)].push_back(i);
		comps[scc.get_comp(i + 1)].push_back(i + 1);
	}
 
	vector<int> val(2 * var_num, -1);
	/*
	 * por cómo funciona nuestro solver de Tarjan, empezar
	 * desde la comp 0 y subir procesa el grafo
	 * en orden topológico inverso — ¿útil, no?
	 */
	for (const vector<int> &comp : comps) {
		int set_to = 1;  // por defecto, todo a verdadero
		// comprobar si algún valor ya tuvo su negación asignada
		for (int v : comp) {
			int neg = v % 2 == 1 ? v - 1 : v + 1;
			if (val[neg] != -1) {
				set_to = !val[neg];
				break;
			}
		}
 
		for (int v : comp) { val[v] = set_to; }
	}
 
	vector<int> actual_val(var_num);
	for (int i = 0; i < var_num; i++) { actual_val[i] = val[2 * i]; }
 
	return actual_val;
}
 
int main() {
	int req_num;
	int topping_num;
	std::cin >> req_num >> topping_num;
	vector<Clause> clauses(req_num);
	for (Clause &c : clauses) {
		char neg1, neg2;
		std::cin >> neg1 >> c.var1 >> neg2 >> c.var2;
		c.var1--;
		c.var2--;
		c.neg1 = neg1 == '-';
		c.neg2 = neg2 == '-';
	}
 
	vector<int> sat_res = solve_sat(clauses, topping_num);
	if (sat_res.empty()) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		for (int t = 0; t < topping_num; t++) {
			cout << (sat_res[t] ? '+' : '-') << " \n"[t == topping_num - 1];
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Unusual Matrix	Fácil	2SAT	—
CF	The Door Problem	Fácil	2SAT, DSU, DFS	—
CC	Hackerman	Fácil	2SAT, DSU, Sliding Window, Greedy	—
Kattis	Illumination	Fácil	2SAT	—
AC	★ Coprime Solitaire	Normal	2SAT	—
CF	★ Babysitting	Difícil	2SAT, Binary Search, Trees	—
CF	★ Harder Satisfiability	Difícil	2SAT, DFS	—