Skip to Content
CTRL K

Even Outdegree Edges

Complejidad temporal: O(N)\mathcal O(N).

Sin pérdida de generalidad, supongamos que el número de aristas es par y que hay solo una componente conexa en el grafo.

Consideremos el siguiente problema más simple: dado un árbol enraizado, orientar las aristas de modo que todos los nodos excepto la raíz tengan grado de salida par; el grado de la raíz puede ser de cualquier paridad.

Podemos resolver este problema más simple de forma recursiva con un DFS. Imaginemos que estamos procesando algún subárbol enraizado en el nodo vv. Primero, procesamos cada uno de los subárboles de los hijos de vv pero aún no orientamos las aristas incidentes de vv. Aunque la paridad del grado de salida de los hijos puede ser arbitraria después de esto, luego podemos orientar cada una de las aristas incidentes de vv para hacerlas todas pares. Esta solución funciona en O(N)\mathcal O(N).

¡Resulta que esto también resuelve la versión del problema en la que la raíz del árbol también debe tener grado de salida par! Esto se debe a que la suma de los grados de salida es igual al número de aristas: como los grados de salida de todos los nodos salvo la raíz son pares, el grado de salida de la raíz también debe ser par.

Para generalizar esta solución a un grafo arbitrario, simplemente:

  1. Hallamos el árbol DFS (que será un árbol de expansión).
  2. Orientamos todas las aristas que no forman parte de este árbol “hacia arriba”.
  3. Ejecutamos la solución para un árbol sobre el árbol DFS (salvo que algunos nodos ahora deben tener grado de salida impar).

El paso 2 funciona porque todas las aristas que no forman parte del árbol DFS son aristas de retroceso (es decir, aristas donde un nodo es padre del otro). Para más información sobre el árbol DFS, léase este post de CF .

Implementación

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[100001];
int visited[100001], odd[100001], timer = 1;
vector<pair<int, int>> ans;
 
void dfs(int node, int parent = 0) {
	visited[node] = timer++;
	for (int i : graph[node])
		if (i != parent) {
			if (!visited[i]) {
				dfs(i, node);
				if (odd[i]) {
					ans.push_back({i, node});
					odd[i] = 0;
				} else {
					ans.push_back({node, i});
					odd[node] ^= 1;
				}
			} else if (visited[node] > visited[i]) {
				ans.push_back({node, i});
				odd[node] ^= 1;
			}
		}
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	scanf("%d %d", &n, &m);
	while (m--) {
		int u, v;
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!visited[i]) dfs(i);
	if (accumulate(odd + 1, odd + n + 1, 0)) printf("IMPOSSIBLE");
	else
		for (pair<int, int> i : ans) printf("%d %d\n", i.first, i.second);
	return 0;
}
import java.io.*;
import java.util.*;
 
public class Main {
	private static final int MAX_N = 100000;
	static List<Integer>[] graph = new ArrayList[MAX_N + 1];
	static int[] visited = new int[MAX_N + 1];
	static int[] odd = new int[MAX_N + 1];
	static int timer = 1;
	static List<Edge> ans = new ArrayList<>();
 
	public static void dfs(int node, int parent) {
		visited[node] = timer++;
		for (int i : graph[node]) {
			if (i == parent) continue;
			if (visited[i] == 0) {
				dfs(i, node);
				if (odd[i] == 1) {
					ans.add(new Edge(i, node));
					odd[i] = 0;
				} else {
					ans.add(new Edge(node, i));
					odd[node] ^= 1;
				}
			} else if (visited[node] > visited[i]) {
				ans.add(new Edge(node, i));
				odd[node] ^= 1;
			}
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); }
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			graph[u].add(v);
			graph[v].add(u);
		}
 
		for (int i = 0; i < n; i++) {
			if (visited[i] == 0) { dfs(i, -1); }
		}
 
		int oddSum = 0;
		for (int i = 0; i < n; i++) { oddSum += odd[i]; }
 
		if (oddSum > 0) {
			pw.println("IMPOSSIBLE");
		} else {
			for (Edge p : ans) { pw.println((p.first + 1) + " " + (p.second + 1)); }
		}
 
		pw.flush();
	}
 
	static class Edge {
		int first, second;
		Edge(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}
}
Fundamentos