War

Explicación

Como la relación de amigos es transitiva, podemos mantener conjuntos en los que todas las personas de un conjunto son amigas. Para cada uno de estos conjuntos de amigos, también habrá un conjunto de enemigos formado por la unión de todos los enemigos de cada persona del conjunto de amigos. Cada persona de este conjunto de enemigos será enemiga de cada persona del conjunto de amigos. Para ver por qué esto es cierto, consideremos una persona $a$ del conjunto de amigos $F$. Su enemigo es $b$ del conjunto de enemigos $E$. Como el enemigo de un amigo también es un enemigo, $b$ será enemigo de todos los amigos de $a$, que son las demás personas de $F$. Además, cada persona de $E$ es amiga de todas las demás personas de $E$, ya que comparten un enemigo común $a$.

Para representar esto, los conjuntos $0 \dots n - 1$ en el código serán conjuntos de amigos, mientras que cada conjunto $i$ en los conjuntos $n \dots 2n - 1$ será el de los enemigos del conjunto $i - n$.

Para cada consulta, hacemos que las dos personas sean $x$ e $y$ y que la raíz de los amigos de $x$, los amigos de $y$, los enemigos de $x$ y los enemigos de $y$ sean $\texttt{xroot}$, $\texttt{yroot}$, $\texttt{exroot}$ y $\texttt{eyroot}$, respectivamente.

areEnemies

Si alguno de los amigos de $x$ es amigo de alguno de los enemigos de $y$, entonces $x$ será amigo de uno de los enemigos de $y$. Así, $x$ e $y$ serán enemigos. Para comprobar si este es el caso, verificamos si $\texttt{xroot}$ es el mismo que $\texttt{eyroot}$ (lo que significa que los amigos de $x$ son los enemigos de $y$), o si $\texttt{yroot}$ es el mismo que $\texttt{exroot}$ (lo que significa que los amigos de $y$ son los enemigos de $x$).

areFriends

Si $x$ e $y$ están en el mismo conjunto, entonces son amigos.

setEnemies

Al marcar a dos personas como enemigas, necesitamos comprobar si son amigas. Podemos usar la función $\texttt{areFriends}$ para esto. Si no son amigas, unimos el conjunto de $\texttt{xroot}$ con el conjunto de $\texttt{eyroot}$ y unimos el conjunto de $\texttt{yroot}$ con el conjunto de $\texttt{exroot}$, ya que el amigo de un enemigo también es un enemigo.

setFriends

Si queremos marcar a dos personas como amigas, primero necesitamos comprobar si son enemigas, usando la función $\texttt{areEnemies}$. Si no son enemigas, podemos unir los conjuntos de $\texttt{xroot}$ y $\texttt{yroot}$. Los enemigos de dos conjuntos de amigos también se volverán amigos, así que también unimos los conjuntos de $\texttt{exroot}$ y $\texttt{eyroot}$.

Implementación

Complejidad temporal: $\mathcal{O}(Q \cdot \alpha(n))$, donde $Q$ es la cantidad de operaciones

#include <algorithm>
#include <iostream>
using namespace std;
int size[20000], parent[20000];
 
void init(int n) {
	for (int i = 0; i < 2 * n; i++) {
		parent[i] = i;
		size[i] = 1;
	}
}
 
int find(int a) {
	if (a == parent[a]) { return a; }
	return parent[a] = find(parent[a]);
}
 
void uniteRoot(int a, int b) {
	if (size[a] > size[b]) { swap(a, b); }
	size[b] += size[a];
	parent[a] = b;
}
 
bool areFriends(int xroot, int yroot) { return xroot == yroot; }
 
bool areEnemies(int xroot, int yroot, int exroot, int eyroot) {
	// x es amigo del enemigo de y
	// o y es amigo del enemigo de x
	return xroot == eyroot || yroot == exroot;
}
 
void setFriends(int xroot, int yroot, int exroot, int eyroot) {
	if (areEnemies(xroot, yroot, exroot, eyroot)) {
		cout << -1 << endl;
		return;
	};
	// si x e y son amigos, entonces
	// los enemigos de x y los enemigos de y también son amigos
	uniteRoot(exroot, eyroot);
	uniteRoot(xroot, yroot);
}
 
void setEnemies(int xroot, int yroot, int exroot, int eyroot) {
	if (areFriends(xroot, yroot)) {
		cout << "-1" << endl;
		return;
	}
	// si x e y son enemigos, entonces
	// x es amigo de los enemigos de y
	// y es amigo de los enemigos de x
	uniteRoot(xroot, eyroot);
	uniteRoot(yroot, exroot);
}
 
int main() {
	int n, c, x, y;
	cin >> n;
	init(n);
	while (cin >> c >> x >> y) {
		if (!c && !x && !y) { break; }
		int xroot = find(x), yroot = find(y);
		int exroot = find(x + n), eyroot = find(y + n);
		if (c == 1) {
			setFriends(xroot, yroot, exroot, eyroot);
		} else if (c == 2) {
			setEnemies(xroot, yroot, exroot, eyroot);
		} else if (c == 3) {
			cout << (areFriends(xroot, yroot) ? 1 : 0) << endl;
		} else {
			cout << (areEnemies(xroot, yroot, exroot, eyroot) ? 1 : 0) << endl;
		}
	}
	return 0;
}