Wizard's Tour

Explicación

En otras palabras, queremos emparejar tantas aristas como sea posible de modo que las aristas de cada par compartan un vértice.

Proponemos dos cosas:

La tarea se puede resolver de forma independiente para cada componente.
La respuesta es siempre $\left\lfloor \frac{m}{2}\right\rfloor$ para una sola componente conexa.

Caso de árbol

Solución

Podemos escribir una función dfs(x,pre) donde x es un vértice del árbol y pre es el vértice padre de x. Esta función emparejará todas las aristas del subárbol de x excepto tal vez la arista que conecta pre y x, según la paridad de la cantidad de aristas de este subárbol. La función devuelve 1 si la arista que conecta pre y x queda sin emparejar y 0 en caso contrario.

C++Java


#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<vector<int>> ans;
 
bool dfs(int x, int pre) {
	vector<int> curr;
	for (int i : adj[x]) {
		if (i != pre) {
			if (dfs(i, x)) {  // arista del árbol de expansión
				curr.push_back(i);
			}
		}
	}
 
	for (int i = 0; i < curr.size() / 2; i++) {
		ans.push_back({curr[2 * i], x, curr[2 * i + 1]});
	}
 
	if (curr.size() % 2 == 0) { return true; }
	if (pre != -1) { ans.push_back({curr[curr.size() - 1], x, pre}); }
 
	return false;
}
 
int main() {
	int n, m;
	cin >> n >> m;
	adj.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	dfs(1, -1);
 
	cout << ans.size() << "\n";
	for (auto a : ans) { cout << a[0] << " " << a[1] << " " << a[2] << "\n"; }
}


import java.io.*;
import java.util.*;
 
public class WizardTour {
	private static List<List<Integer>> adj;
	private static List<int[]> ans;
 
	private static boolean dfs(int x, int pre) {
		List<Integer> curr = new ArrayList<>();
		for (int i : adj.get(x)) {
			if (i != pre) {
				if (dfs(i, x)) {  // arista del árbol de expansión
					curr.add(i);
				}
			}
		}
 
		for (int i = 0; i < curr.size() / 2; i++) {
			ans.add(new int[] {curr.get(2 * i), x, curr.get(2 * i + 1)});
		}
		if (curr.size() % 2 == 0) { return true; }
		if (pre != -1) { ans.add(new int[] {curr.get(curr.size() - 1), x, pre}); }
 
		return false;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		adj = new ArrayList<>(n + 1);
		for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); }
		ans = new ArrayList<>();
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		dfs(1, -1);
 
		System.out.println(ans.size());
		for (int[] a : ans) { System.out.println(a[0] + " " + a[1] + " " + a[2]); }
	}
}

Caso general

Solución

Primero, hallamos cualquier árbol de expansión. Luego, para cada arista $(a,b)$ que no está en el árbol de expansión, desconectamos uno de sus extremos (no importa cuál). Por ejemplo, si desconectamos $b$ tratamos la arista como $(a,x)$ en su lugar, donde $x$ solo está conectado a $a$ . Esto reduce el problema al caso de árbol.

Solo hay que modificar un poco la solución de arriba. Aquí desconectamos la arista $(x,i)$ de $i$ cuando $x<i$ ( $x>i$ funcionaría igual de bien).

C++Java


#include <bits/stdc++.h>
using namespace std;
 
vector<bool> visited;
vector<vector<int>> adj;
vector<vector<int>> ans;
 
bool dfs(int x, int pre) {
	visited[x] = true;
	vector<int> curr;
	for (int i : adj[x]) {
		if (i != pre) {
			if (visited[i]) {  // arista que no es del árbol de expansión
				if (x < i) { curr.push_back(i); }
			} else if (dfs(i, x)) {
				curr.push_back(i);  // arista del árbol de expansión
			}
		}
	}
 
	for (int i = 0; i < curr.size() / 2; i++) {
		ans.push_back({curr[2 * i], x, curr[2 * i + 1]});
	}
 
	if (curr.size() % 2 == 0) { return true; }
	if (pre != -1) { ans.push_back({curr[curr.size() - 1], x, pre}); }
 
	return false;
}
 
int main() {
	int n, m;
	cin >> n >> m;
	adj.resize(n + 1);
	visited.resize(n + 1, false);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) { dfs(i, -1); }
	}
 
	cout << ans.size() << "\n";
	for (auto a : ans) { cout << a[0] << " " << a[1] << " " << a[2] << "\n"; }
}


import java.io.*;
import java.util.*;
 
public class WizardTour {
	private static boolean[] visited;
	private static List<List<Integer>> adj;
	private static List<int[]> ans;
 
	private static boolean dfs(int x, int pre) {
		visited[x] = true;
		List<Integer> curr = new ArrayList<>();
		for (int i : adj.get(x)) {
			if (i != pre) {
				if (visited[i]) {  // arista que no es del árbol de expansión
					if (x < i) { curr.add(i); }
				} else if (dfs(i, x)) {
					curr.add(i);  // arista del árbol de expansión
				}
			}
		}
 
		for (int i = 0; i < curr.size() / 2; i++) {
			ans.add(new int[] {curr.get(2 * i), x, curr.get(2 * i + 1)});
		}
		if (curr.size() % 2 == 0) { return true; }
		if (pre != -1) { ans.add(new int[] {curr.get(curr.size() - 1), x, pre}); }
 
		return false;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		visited = new boolean[n + 1];
		adj = new ArrayList<>(n + 1);
		for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); }
		ans = new ArrayList<>();
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) { dfs(i, -1); }
		}
 
		System.out.println(ans.size());
		for (int[] a : ans) { System.out.println(a[0] + " " + a[1] + " " + a[2]); }
	}
}