Split Into Two Sets

Editorial oficial (C++) 

Explicación

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

Primero observemos que si algún número está presente en más de 2 fichas de dominó o si una ficha tiene el mismo número repetido dos veces, entonces es imposible crear los 2 conjuntos. Esto se debe a que ambos casos harían que un grupo tuviera dos números (no podemos meter 3 ítems en 2 grupos sin que eso ocurra).

Podemos convertir este problema en un problema de grafos dibujando aristas entre fichas que comparten números (la motivación principal es que tenemos 2 conjuntos, lo que nos recuerda a las particiones bipartitas). En concreto, sea la ficha $i$ la que tiene los dos números $a_i$ y $b_i$. Entonces dibujamos una arista entre las fichas $i$ y $j$ si y solo si $a_i = a_j$ o $a_i = b_j$ o $a_j = b_i$ o $a_j = b_j$.

Ahora, supongamos que tenemos una forma de crear los 2 conjuntos, con $\frac{n}2$ fichas en cada conjunto. Como cada número aparece solo una vez en cada conjunto, este grafo es bipartito.

Esto nos lleva a la siguiente afirmación: es posible construir los dos conjuntos si y solo si  el grafo construido como arriba es bipartito. Demostramos la cláusula “solo si” arriba; solo resta demostrar la cláusula “si”.

Supongamos que el grafo es bipartito. Dividimos el grafo en dos conjuntos según la partición bipartita del grafo. Queremos demostrar que ningún número se repite dos veces en ninguno de estos conjuntos. Sin embargo, como existe una arista entre cualesquiera dos fichas que comparten un número, es imposible que dos fichas que comparten un número estén en el mismo conjunto (si fuera posible, tendríamos un ciclo de longitud 1, que es impar, contradiciendo que el grafo es bipartito). Así, dada una partición bipartita del grafo, podemos construir fácilmente nuestros 2 conjuntos deseados.

La implementación de esto es relativamente directa: simplemente comprobamos si el grafo es bipartito o no, y damos la salida en consecuencia.

#include <bits/stdc++.h>
using namespace std;
 
bool dfs(int u, int color, vector<int> &vis, vector<vector<int>> &adj) {
	// Si el nodo ya fue visitado y estaba marcado con el mismo color
	if (vis[u] == color) { return true; }
 
	// Si el nodo ya fue visitado y estaba marcado con el otro color
	if (vis[u] == 1 - color) { return false; }
 
	vis[u] = color;
	for (int v : adj[u]) {
		if (!dfs(v, 1 - color, vis, adj)) return false;
	}
	return true;
}
 
void solve() {
	int n;
	cin >> n;
	vector<pair<int, int>> dominoes(n);
 
	for (pair<int, int> &i : dominoes) { cin >> i.first >> i.second; }
 
	for (pair<int, int> i : dominoes) {
		// Comprobar si un número de la ficha está repetido
		if (i.first == i.second) {
			cout << "NO\n";
			return;
		}
	}
 
	map<int, vector<int>> color_to_index;
	for (int i = 0; i < n; i++) {
		color_to_index[dominoes[i].first].push_back(i);
		color_to_index[dominoes[i].second].push_back(i);
		// Comprobar si un número existe en 3 o más fichas
		if (color_to_index[dominoes[i].first].size() > 2 ||
		    color_to_index[dominoes[i].second].size() > 2) {
			cout << "NO\n";
			return;
		}
	}
 
	// inicializar variables para DFS
	vector<int> vis(n, -1);
	vector<vector<int>> adj(n);
	for (pair<int, vector<int>> p : color_to_index) {
		vector<int> v = p.second;
		if (v.size() == 2) {
			adj[v[0]].push_back(v[1]);
			adj[v[1]].push_back(v[0]);
		}
	}
 
	for (int i = 0; i < n; i++) {
		if (vis[i] == -1) {
			if (!dfs(i, 0, vis, adj)) {
				cout << "NO" << endl;
				return;
			}
		}
	}
	cout << "YES" << endl;
}
 
int main() {
	int t;
	cin >> t;
	for (int test = 0; test < t; test++) { solve(); }
}