Recorrido de grafos

Introducción

Recursos
Fuente	Recurso	Notas
CPH	12 - Graph traversal

Los algoritmos de recorrido de grafos visitan todos los nodos de un grafo en cierto orden y pueden calcular información a lo largo del camino. Dos algoritmos habituales para esto son la búsqueda en profundidad (DFS) y la búsqueda en anchura (BFS).

Aplicación: componentes conexas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Building Roads	Fácil	Connected Components	en el módulo

Una componente conexa es un conjunto maximal de nodos conexos en un grafo no dirigido. En otras palabras, dos nodos están en la misma componente conexa si y solo si pueden alcanzarse entre sí a través de aristas del grafo.

En el problema foco de arriba, el objetivo es agregar la menor cantidad posible de aristas de modo que el grafo entero forme una sola componente conexa.

Aplicación: bicoloreo de grafos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Building Teams	Fácil	Bipartite	en el módulo

El bicoloreo de grafos consiste en asignar un valor booleano a cada nodo del grafo, dictado por la configuración de las aristas. El ejemplo más común de un grafo bicoloreado es un grafo bipartito, en el que cada arista conecta dos nodos de colores opuestos.

En el problema foco de arriba, el objetivo es asignar cada nodo (amigo) del grafo a uno de dos colores (equipos), sujeto a la restricción de que las aristas (amistades) conecten dos nodos de colores opuestos. En otras palabras, hay que verificar si la entrada es un grafo bipartito y emitir un coloreo válido si lo es.

DFS

Recursos
Fuente	Recurso	Notas
CSA	Depth First Search	hasta, pero sin incluir, “More about DFS”
CPH	12.1 - DFS	diagrama de ejemplo + código

Video de YouTube (7Qta1VQiTlI)

Del segundo recurso:

La búsqueda en profundidad (DFS) es una técnica directa de recorrido de grafos. El algoritmo empieza en un nodo inicial y avanza hacia todos los demás nodos que son alcanzables desde el nodo inicial usando las aristas del grafo.

La búsqueda en profundidad siempre sigue un único camino en el grafo mientras encuentre nodos nuevos. Después de eso, vuelve a nodos anteriores y empieza a explorar otras partes del grafo. El algoritmo lleva la cuenta de los nodos visitados, de modo que procesa cada nodo una sola vez.

Al implementar DFS, a menudo usamos una función recursiva para visitar los vértices y un arreglo para guardar si ya vimos un vértice.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int n = 6;
vector<vector<int>> adj(n);
vector<bool> visited(n);
 
void dfs(int current_node) {
	if (visited[current_node]) { return; }
	visited[current_node] = true;
 
	for (int neighbor : adj[current_node]) { dfs(neighbor); }
}
 
int main() {
	/*
	 * Definir la lista de adyacencia y leer la entrada específica del problema
	 *
	 * En este ejemplo, dimos una "entrada dummy" que
	 * se refleja en el GIF de arriba para ilustrar el
	 * orden de las llamadas recursivas.
	 */
	adj[0] = {1, 2, 4};
	adj[1] = {3, 4};
	adj[2] = {5};
 
	for (int i = 0; i < n; i++) {
		// iterar sobre todas las componentes conexas del grafo
		if (!visited[i]) { dfs(i); }
	}
}


import java.io.*;
import java.util.*;
 
public class DFSDemo {
	static List<Integer>[] adj;
	static boolean[] visited;
	static int n = 6;
 
	public static void main(String[] args) throws IOException {
		visited = new boolean[n];
 
		/*
		 * Definir la lista de adyacencia y leer la entrada específica del problema
		 *
		 * En este ejemplo, dimos una "entrada dummy" que
		 * se refleja en el GIF de arriba para ilustrar el
		 * orden de las llamadas recursivas.
		 */
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		adj[0] = new ArrayList<>(Arrays.asList(1, 2, 4));
		adj[1] = new ArrayList<>(Arrays.asList(3, 4));
		adj[2] = new ArrayList<>(Arrays.asList(5));
 
		for (int i = 0; i < n; i++) {
			// iterar sobre todas las componentes conexas del grafo
			if (!visited[i]) { dfs(i); }
		}
	}
 
	static void dfs(int currentNode) {
		if (visited[currentNode]) { return; }
 
		visited[currentNode] = true;
		for (int neighbor : adj[currentNode]) { dfs(neighbor); }
	}
}


import sys
 
sys.setrecursionlimit(10**5)  # Python tiene un límite de recursión por defecto de 1000
 
n = 6
visited = [False] * n
 
"""
Definir la lista de adyacencia y leer la entrada específica del problema.
 
En este ejemplo, dimos una "entrada dummy" que
se refleja en el GIF de arriba para ilustrar el
orden de las llamadas recursivas.
"""
adj = [[] for _ in range(n)]
adj[0] = [1, 2, 4]
adj[1] = [3, 4]
adj[2] = [5]
 
 
def dfs(current_node):
	visited[current_node] = True
	for neighbor in adj[current_node]:
		if not visited[neighbor]:
			dfs(neighbor)
 
 
for i in range(n):
	if not visited[i]:
		dfs(i)

BFS

Recursos
Fuente	Recurso	Notas
CSA	BFS	interactivo, implementación
PAPS1	8.3 - BFS	ejemplos de grilla y 8-puzzle
cp-algo	BFS	aplicaciones comunes
KA	BFS and its uses
YouTube	Breadth First Search Algorithm	Si se prefiere el formato video

En una búsqueda en anchura, recorremos los vértices en orden de su distancia al vértice de partida.

Prerrequisito - Colas y deques

Recursos
Fuente	Recurso	Notas
CPH	4.5 - Queues, Deques
PAPS1	6.3 - Queues

Colas

Una cola es una estructura de datos FIFO (First In First Out) que soporta tres operaciones, todas en tiempo $\mathcal{O}(1)$ .

C++JavaPython

std::queue

push: inserta al final de la cola
pop: elimina del frente de la cola
front: obtiene el elemento del frente sin quitarlo.


queue<int> q;
q.push(1);                  // [1]
q.push(3);                  // [3, 1]
q.push(4);                  // [4, 3, 1]
q.pop();                    // [4, 3]
cout << q.front() << endl;  // 3

add: inserción al final de la cola
poll: eliminación del frente de la cola
peek: obtiene el elemento del frente sin quitarlo

Java no tiene realmente una clase Queue; solo es una interfaz. La implementación más usada es LinkedList, declarada así:


Queue<Integer> q = new LinkedList<Integer>();
q.add(1);                      // [1]
q.add(3);                      // [3, 1]
q.add(4);                      // [4, 3, 1]
q.poll();                      // [4, 3]
System.out.println(q.peek());  // 3

Python tiene un módulo builtin queue.

Queue.put(n): Inserta el elemento al final de la cola.
Queue.get(): Obtiene y quita el elemento del frente. Si la cola está vacía, esto espera para siempre, generando un error TLE.
Queue.queue[n]: Obtiene el n-ésimo elemento sin quitarlo. Poner n en 0 para el primer elemento.


from queue import Queue
 
q = Queue()  # []
q.put(1)  # [1]
q.put(2)  # [1, 2]
v = q.queue[0]  # v = 1, q = [1, 2]
v = q.get()  # v = 1, q = [2]
v = q.get()  # v = 2, q = []
v = q.get()  # El código espera para siempre, generando un error TLE.

Deques

Un deque (suele pronunciarse “deck”) significa double-ended queue y es una combinación de una pila y una cola, en el sentido de que soporta inserciones y eliminaciones en $\mathcal{O}(1)$ tanto del frente como del final del deque. No es muy común en Bronce / Plata.

C++JavaPython

std::deque

Los cuatro métodos para agregar y quitar son push_back, pop_back, push_front y pop_front.


deque<int> d;
d.push_front(3);  // [3]
d.push_front(4);  // [4, 3]
d.push_back(7);   // [4, 3, 7]
d.pop_front();    // [3, 7]
d.push_front(1);  // [1, 3, 7]
d.pop_back();     // [1, 3]

También se puede acceder a un deque en tiempo constante como a un arreglo con el operador []. Por ejemplo, para acceder al $i$ -ésimo elemento de un deque $\texttt{dq}$ , se hace $\texttt{dq}[i]$ .

En Java, la clase de deque se llama ArrayDeque. Los cuatro métodos para agregar y quitar son addFirst, removeFirst, addLast y removeLast.


ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
deque.addFirst(3);    // [3]
deque.addFirst(4);    // [4, 3]
deque.addLast(7);     // [4, 3, 7]
deque.removeFirst();  // [3, 7]
deque.addFirst(1);    // [1, 3, 7]
deque.removeLast();   // [1, 3]

En Python, collections.deque() se usa como estructura de datos deque. Los cuatro métodos para agregar y quitar son appendleft, popleft, append y pop.


d = collections.deque()
d.appendleft(3)  # [3]
d.appendleft(4)  # [4, 3]
d.append(7)  # [4, 3, 7]
d.popleft()  # [3, 7]
d.appendleft(1)  # [1, 3, 7]
d.pop()  # [1, 3]

Implementación

Al implementar BFS, a menudo usamos una cola para llevar la cuenta del siguiente vértice a visitar. Como en DFS, también vamos a mantener un arreglo para guardar si ya vimos un vértice.

JavaC++Python


import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		int n = 6;
		boolean[] visited = new boolean[n];
		List<Integer>[] adj = new ArrayList[6];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		adj[0] = new ArrayList<>(Arrays.asList(1, 2, 4));
		adj[1] = new ArrayList<>(Arrays.asList(3, 4));
		adj[2] = new ArrayList<>(Arrays.asList(5));
 
		/*
		 * Definir la lista de adyacencia y leer la entrada específica del problema
		 *
		 * En este ejemplo, dimos una "entrada dummy" que
		 * se refleja en el GIF de arriba para ilustrar el
		 * orden de las llamadas recursivas.
		 */
		for (int i = 0; i < n; i++) {
			// iterar sobre todas las componentes conexas del grafo
			if (!visited[i]) {
				Queue<Integer> q = new LinkedList<Integer>();
				q.add(i);
 
				while (q.size() > 0) {
					int currentNode = q.peek();
					q.poll();
 
					visited[currentNode] = true;
 
					for (int neighbor : adj[currentNode]) {
						if (!visited[neighbor]) { q.add(neighbor); }
					}
				}
			}
		}
	}
}


#include <queue>
#include <vector>
 
using std::queue;
using std::vector;
 
int main() {
	int n = 6;
	vector<vector<int>> adj(n);
	vector<bool> visited(n);
 
	/*
	 * Definir la lista de adyacencia y leer la entrada específica del problema
	 *
	 * En este ejemplo, dimos una "entrada dummy" que
	 * se refleja en el GIF de arriba para ilustrar el
	 * orden de las llamadas recursivas.
	 */
	adj[0] = {1, 2, 4};
	adj[1] = {3, 4};
	adj[2] = {5};
 
	for (int i = 0; i < n; i++) {
		// iterar sobre todas las componentes conexas del grafo
		if (!visited[i]) {
			queue<int> q;
			q.push(i);
			visited[i] = true;
			while (!q.empty()) {
				int current_node = q.front();
				q.pop();
				for (int neighbor : adj[current_node]) {
					if (!visited[neighbor]) {
						visited[neighbor] = true;
						q.push(neighbor);
					}
				}
			}
		}
	}
}


from collections import deque
 
"""
Definir la lista de adyacencia y leer la entrada específica del problema
 
En este ejemplo, dimos una "entrada dummy" que
se refleja en el GIF de arriba para ilustrar el
orden de las llamadas recursivas.
"""
 
n = 6
adj = [[] for _ in range(n)]
visited = [False] * n
 
adj[0] = [1, 2, 4]
adj[1] = [3, 4]
adj[2] = [5]
 
for i in range(n):
	# iterar sobre todas las componentes conexas del grafo
	if not visited[i]:
		q = deque([i])
 
		while q:
			node = q.popleft()
			visited[node] = True
 
			for neighbor in adj[node]:
				if not visited[neighbor]:
					q.append(neighbor)

Solución - Building Roads

Nótese que cada arista disminuye la cantidad de componentes conexas en cero o en uno. Así que hay que agregar al menos $C-1$ aristas, donde $C$ es la cantidad de componentes conexas del grafo de entrada.

Para calcular $C$ , iteramos por cada nodo. Si no se visitó, lo visitamos junto con todos los demás nodos de su componente conexa usando DFS o BFS. Entonces $C$ es igual a la cantidad de veces que realizamos la operación de visita.

Hay muchas formas válidas de elegir $C-1$ caminos nuevos para construir. Una forma es elegir un único representante de cada una de las $C$ componentes y unirlos en una línea.

Solución DFS

C++JavaPython


#include <deque>
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> adj;
vector<bool> visited;
 
void dfs(int node) {
	for (int n : adj[node]) {
		if (!visited[n]) {
			visited[n] = true;
			dfs(n);
		}
	}
}
 
int main() {
	int n;
	int m;
	cin >> n >> m;
	adj = vector<vector<int>>(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	visited = vector<bool>(n);
	vector<int> city_reps;
	for (int i = 0; i < n; i++) {
		if (visited[i]) { continue; }
 
		visited[i] = true;
		city_reps.push_back(i);
		dfs(i);
	}
 
	cout << city_reps.size() - 1 << '\n';
	for (int i = 0; i < city_reps.size() - 1; i++) {
		cout << city_reps[i] + 1 << ' ' << city_reps[i + 1] + 1 << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class BuildingRoads {
	static List<Integer>[] adj;
	static boolean[] visited;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		visited = new boolean[n];
		List<Integer> cityReps = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			if (visited[i]) { continue; }
 
			visited[i] = true;
			cityReps.add(i);
			dfs(i);
		}
 
		StringBuilder ans = new StringBuilder();
		ans.append(cityReps.size() - 1).append('\n');
		for (int i = 0; i < cityReps.size() - 1; i++) {
			ans.append(cityReps.get(i) + 1)
			    .append(' ')
			    .append(cityReps.get(i + 1) + 1)
			    .append('\n');
		}
		io.println(ans);
		io.close();
	}
 
	static void dfs(int node) {
		for (int n : adj[node]) {
			if (!visited[n]) {
				visited[n] = true;
				dfs(n);
			}
		}
	}
 
	// CodeSnip{Kattio}
}


from collections import deque
 
n, m = map(int, input().split())
 
adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
 
 
def dfs(node: int) -> None:
	for n in adj[node]:
		if not visited[n]:
			visited[n] = True
			dfs(n)
 
 
visited = [False for _ in range(n)]
rep_cities = []
for i in range(n):
	if visited[i]:
		continue
 
	visited[i] = True
	rep_cities.append(i)
	dfs(i)
 
print(len(rep_cities) - 1)
for i in range(len(rep_cities) - 1):
	print(rep_cities[i] + 1, rep_cities[i + 1] + 1)

Sin embargo, este código causa un error de ejecución en casi la mitad de los casos de prueba. ¿Qué puede estar fallando?

Un problema con la recursión profunda

Si se corre el código de la solución en local sobre el grafo línea generado por el siguiente código de Python:


n = 100000
print(n, n - 1)
for i in range(1, n):
	print(i, i + 1)

C++JavaPython

entonces se puede obtener un segmentation fault aunque el código pase en el juez online. Esto ocurre porque cada llamada recursiva contribuye al tamaño de la pila de llamadas , que está limitada a unos pocos megabytes por defecto. Para aumentar el tamaño de la pila, ver este módulo. Respuesta corta: si normalmente se compila el código con g++ sol.cpp, entonces hay que compilarlo con g++ -Wl,-stack_size,0xF0000000 sol.cpp en su lugar.

entonces se puede obtener un StackOverflowError aunque el código pase en el juez online. Esto ocurre porque cada llamada recursiva contribuye al tamaño de la pila de llamadas , que está limitada a menos de un megabyte por defecto. Para resolverlo, se puede pasar una opción de la forma -Xss... para correr el código con un tamaño de pila mayor. Por ejemplo, java -Xss512m Main corre el código con un límite de pila de 512 megabytes.

entonces se observa un RecursionError que se ve así:


Traceback (most recent call last):
  File "input/code.py", line 28, in <module>
	solve(n, adj)
  File "input/code.py", line 14, in solve
	dfs(start, start)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  [Previous line repeated 994 more times]
  File "input/code.py", line 7, in dfs
	if next in unvisited:
RecursionError: maximum recursion depth exceeded in comparison

Esto ocurre para $N>10^3$ porque el límite de recursión en Python está puesto en 1000 por defecto. Se puede corregir aumentando el límite de recursión con sys.setrecursionlimit(10 ** 6), aunque igual obtenemos TLE en dos casos de prueba. Para resolverlo, podemos implementar una solución BFS, como se muestra abajo.

Solución BFS

C++JavaPython


#include <deque>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	int m;
	cin >> n >> m;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	vector<bool> visited(n);
	vector<int> city_reps;
	for (int i = 0; i < n; i++) {
		if (visited[i]) { continue; }
 
		visited[i] = true;
		city_reps.push_back(i);
		deque<int> todo{i};
		while (!todo.empty()) {
			int curr = todo.front();
			todo.pop_front();
			for (int next : adj[curr]) {
				if (!visited[next]) {
					visited[next] = true;
					todo.push_back(next);
				}
			}
		}
	}
 
	cout << city_reps.size() - 1 << '\n';
	for (int i = 0; i < city_reps.size() - 1; i++) {
		cout << city_reps[i] + 1 << ' ' << city_reps[i + 1] + 1 << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class BuildingRoads {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		List<Integer>[] adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		boolean[] visited = new boolean[n];
		List<Integer> cityReps = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			if (visited[i]) { continue; }
 
			visited[i] = true;
			cityReps.add(i);
			ArrayDeque<Integer> todo = new ArrayDeque<>();
			todo.add(i);
			while (!todo.isEmpty()) {
				int curr = todo.poll();
				for (int next : adj[curr]) {
					if (!visited[next]) {
						visited[next] = true;
						todo.add(next);
					}
				}
			}
		}
 
		StringBuilder ans = new StringBuilder();
		ans.append(cityReps.size() - 1).append('\n');
		for (int i = 0; i < cityReps.size() - 1; i++) {
			ans.append(cityReps.get(i) + 1)
			    .append(' ')
			    .append(cityReps.get(i + 1) + 1)
			    .append('\n');
		}
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


from collections import deque
 
n, m = map(int, input().split())
 
adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
 
visited = [False for _ in range(n)]
city_reps = []
for i in range(n):
	if visited[i]:
		continue
 
	visited[i] = True
	city_reps.append(i)
	todo = deque([i])
	while todo:
		curr = todo.popleft()
		for next_ in adj[curr]:
			if not visited[next_]:
				visited[next_] = True
				todo.append(next_)
 
print(len(city_reps) - 1)
for i in range(len(city_reps) - 1):
	print(city_reps[i] + 1, city_reps[i + 1] + 1)

Problemas de componentes conexas

Fuente	Nombre	Dificultad	Tags	Solución
Silver	Closing the Farm	Fácil	Connected Components	Solución
Silver	★ Moocast	Fácil	Connected Components, DFS, BFS	Solución
Silver	★ Fence Planning	Fácil	Connected Components	Solución
Kattis	Birthday Party	Fácil	Connected Components	Solución
ACSL	Rank	Fácil	DFS	Solución
CSES	★ Flight Routes Check	Normal	DFS	Solución
CSA	BFS-DFS	Normal	BFS, DFS	Solución
Gold	Moocast	Normal	Connected Components, Binary Search	Solución
Silver	★ Wormhole Sort	Normal	Connected Components, Binary Search	Solución
Silver	Moo Route II	Normal	BFS	—
Silver	Connecting Two Barns	Normal	Connected Components, 2P, Binary Search	Solución
Silver	Redistributing Gifts	Normal	DFS	Solución
CF	Round Dance	Normal	DFS, Connected Components	Solución
CSES	Subarray Sum Constraints	Normal	DFS, Connected Components, Prefix Sums	Solución
CF	Connected Components?	Difícil	DFS, Sorted Set	Solución
Kattis	Lane Switching	Muy difícil	Connected Components, Binary Search	Solución
Silver	Cereal 2	Muy difícil	Spanning Tree, Constructive, Cycles	—

Solución - Building Teams

Recursos
Fuente	Recurso	Notas
CPH	12.3 - Bipartiteness check	Esbozo breve de la solución con diagramas.
IUSACO	10.7 - Bipartite Graphs
cp-algo	Bipartite Check
CP2	4.2.6 - Bipartite Check

Para cada componente conexa, podemos etiquetar un nodo de forma arbitraria y luego correr DFS o BFS. Cada vez que visitamos un nodo nuevo (no visitado), fijamos su color según la regla de las aristas. Cuando visitamos un nodo ya visitado, comprobamos si su color cumple la regla de las aristas.

Solución DFS

Lista de adyacencia sin un arreglo de vectors

Ver acá .

C++JavaPython


#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> assigned;
vector<vector<int>> adj;
 
/** @return true solo si es posible asignar cada persona a un equipo */
bool dfs(int node) {
	int curr = assigned[node];
	int nColor = curr == 1 ? 2 : 1;  // El color que deberían tener los vecinos
	for (int n : adj[node]) {
		if (assigned[n] != 0) {
			// Comprobar si el color que ya existe coincide
			if (assigned[n] != nColor) { return false; }
		} else {
			assigned[n] = nColor;
			if (!dfs(n)) {
				return false;  // Paramos en cuanto encontramos una contradicción
			}
		}
	}
	return true;
}
 
int main() {
	int n;
	int m;
	cin >> n >> m;
	adj = vector<vector<int>>(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	assigned = vector<int>(n);
	bool valid = true;
	for (int i = 0; i < n; i++) {
		if (assigned[i] == 0) {
			assigned[i] = 1;  // Asignar un equipo inicial arbitrario
			if (!dfs(i)) {
				valid = false;
				break;
			}
		}
	}
 
	if (valid) {
		for (int i = 0; i < n; i++) { cout << assigned[i] << " \n"[i == n - 1]; }
	} else {
		cout << "IMPOSSIBLE" << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class BuildingTeams {
	static List<Integer>[] adj;
	static int[] assigned;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		assigned = new int[n];
		boolean valid = true;
		for (int i = 0; i < n; i++) {
			if (assigned[i] == 0) {
				assigned[i] = 1;  // Asignar un equipo inicial arbitrario
				if (!dfs(i)) {
					valid = false;
					break;
				}
			}
		}
 
		if (valid) {
			for (int i = 0; i < n - 1; i++) { io.print(assigned[i] + " "); }
			io.println(assigned[n - 1]);
		} else {
			io.println("IMPOSSIBLE");
		}
	}
 
	/** @return si es posible asignar cada persona a un equipo */
	static boolean dfs(int node) {
		int curr = assigned[node];
		int nColor = curr == 1 ? 2 : 1;  // El color que deberían tener los vecinos
		for (int n : adj[node]) {
			if (assigned[n] != 0) {
				// Comprobar si el color que ya existe coincide
				if (assigned[n] != nColor) { return false; }
			} else {
				assigned[n] = nColor;
				if (!dfs(n)) {
					return false;  // Paramos en cuanto encontramos una contradicción
				}
			}
		}
		return true;
	}
 
	// CodeSnip{Kattio}
}


import sys
 
input = sys.stdin.readline
 
sys.setrecursionlimit(int(1e9))  # desactivar el límite de recursión
 
n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
team = [0] * n  # 0: todavía no asignado, 1: equipo 1, 2: equipo 2
 
for _ in range(m):
	a, b = map(int, map(int, input().strip().split()))
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
 
 
def dfs(node: int):
	for next_node in adj[node]:
		if team[next_node]:
			if team[next_node] == team[node]:
				print("IMPOSSIBLE")
				exit()
		else:
			team[next_node] = 2 if team[node] == 1 else 1
			dfs(next_node)
 
 
for node in range(n):
	if not team[node]:
		team[node] = 1
		dfs(node)
 
print(*team)

Solución BFS

Los detalles del algoritmo son casi exactamente los mismos; solo que los hacemos de forma iterativa en lugar de recursiva.

C++JavaPython


#include <deque>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	int m;
	cin >> n >> m;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	vector<int> assigned(n);
	bool valid = true;
	for (int i = 0; i < n; i++) {
		if (assigned[i] != 0) { continue; }
 
		assigned[i] = 1;
		deque<int> todo{i};
		while (!todo.empty()) {
			int curr = todo.front();
			todo.pop_front();
			int n_color = assigned[curr] == 1 ? 2 : 1;
			for (int next : adj[curr]) {
				if (assigned[next] != 0) {
					if (assigned[next] != n_color) {
						valid = false;
						goto end;
					}
				} else {
					assigned[next] = n_color;
					todo.push_back(next);
				}
			}
		}
	}
end:;
 
	if (valid) {
		for (int i = 0; i < n; i++) { cout << assigned[i] << " \n"[i == n - 1]; }
	} else {
		cout << "IMPOSSIBLE" << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class BuildingTeams {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		List<Integer>[] adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		int[] assigned = new int[n];
		boolean valid = true;
	search:
		for (int i = 0; i < n; i++) {
			if (assigned[i] != 0) { continue; }
 
			assigned[i] = 1;
			ArrayDeque<Integer> todo = new ArrayDeque<>();
			todo.add(i);
			while (!todo.isEmpty()) {
				int curr = todo.poll();
				int nColor = assigned[curr] == 1 ? 2 : 1;
				for (int next : adj[curr]) {
					if (assigned[next] != 0) {
						if (assigned[next] != nColor) {
							valid = false;
							break search;
						}
					} else {
						assigned[next] = nColor;
						todo.push(next);
					}
				}
			}
		}
 
		if (valid) {
			for (int i = 0; i < n - 1; i++) { io.print(assigned[i] + " "); }
			io.println(assigned[n - 1]);
		} else {
			io.println("IMPOSSIBLE");
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}


from collections import deque
 
n, m = map(int, input().split())
 
adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
 
assigned = [0 for _ in range(n)]
valid = True
for i in range(n):
	if assigned[i] != 0:
		continue
 
	assigned[i] = 1
	todo = deque([i])
	while todo:
		curr = todo.popleft()
		n_color = 2 if assigned[curr] == 1 else 1
		for next_ in adj[curr]:
			if assigned[next_] != 0:
				if assigned[next_] != n_color:
					valid = False
					break
			else:
				assigned[next_] = n_color
				todo.append(next_)
 
		if not valid:
			break
 
	if not valid:
		break
 
if valid:
	print(*assigned)
else:
	print("IMPOSSIBLE")

Problemas de bicoloreo de grafos

Fuente	Nombre	Dificultad	Tags	Solución
CF	Bipartiteness	Fácil	Bipartite	Solución
Silver	★ The Great Revegetation	Fácil	Bipartite	Solución
CF	Cover it!	Fácil	Bipartite	Solución
Baltic OI	2020 - Graph	Difícil	DFS, Median	Solución
CC	Among Us	Difícil	DFS, Bipartite	Solución
CF	Coloring Game	Difícil	DFS, Bipartite	Solución
CF	Catshock	Difícil	Trees, Bipartite	—
APIO	2011 - Table Coloring	Muy difícil	Bipartite	Solución

Quiz

Pregunta 1/4

¿Cuál es la diferencia principal entre DFS y BFS?