Among Us

Explicación

Si solo tenemos dos jugadores $x$ e $y$ , entonces hay 4 casos.

Si $x$ respalda a $y$ y $x$ es un impostor, entonces $y$ también debe ser un impostor.
Si $x$ respalda a $y$ y $x$ es un tripulante, entonces $y$ también debe ser un tripulante.
Si $x$ acusa a $y$ de ser un impostor y $x$ es un impostor, entonces $y$ debe ser un tripulante.
Si $x$ acusa a $y$ de ser un impostor y $x$ es un tripulante, entonces $y$ debe ser un impostor.

Se nota que siempre que $x$ acusa a $y$ , serán de tipos distintos, y cuando $x$ respalda a $y$ , serán del mismo tipo.

Con esta información, podemos construir un grafo bipartito y colorear nodos del mismo color si se respaldan entre sí, o de colores distintos si uno acusa al otro. Si no podemos construir este grafo, entonces no puede existir una disposición válida.

En caso contrario, consideramos cada componente conexa de forma independiente y llevamos la cuenta de la cantidad de tripulantes e impostores. Al final, devolvemos la suma del máximo de estos dos valores para todas las componentes conexas. No nos importan los roles de cada nodo porque podemos intercambiarlos todos para obtener otra solución válida.

Implementación

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

C++JavaPython


#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
int main() {
	int t;
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		int n;
		int q;
		cin >> n >> q;
 
		// adj[i][j] = {el j-ésimo nodo adyacente desde i
		// su declaración (0 = impostor, 1 = tripulante)}
		vector<vector<pair<int, bool>>> adj(n);
		for (int i = 0; i < q; i++) {
			int type;
			int x;
			int y;
			cin >> type >> x >> y;
			--x;
			--y;
			--type;
 
			adj[x].push_back({y, type});
			adj[y].push_back({x, type});
		}
 
		vector<int> role(n, -1);
 
		int ans = 0;
		bool impossible = false;
		for (int i = 0; i < n; i++) {
			// aún no visitamos esta componente conexa
			if (role[i] == -1) {
				int imposters = 0, crewmates = 0;
 
				// dfs para construir el grafo bipartito
				stack<int> todo;
 
				todo.push(i);
				role[i] = true;
				imposters++;
 
				while (!todo.empty()) {
					int curr = todo.top();
					todo.pop();
 
					for (pair<int, bool> u : adj[curr]) {
						bool type = u.second ? role[curr] : !role[curr];
 
						// no visitado
						if (role[u.first] == -1) {
							role[u.first] = type;
 
							if (type) {
								imposters++;
							} else {
								crewmates++;
							}
 
							todo.push(u.first);
							// crea una contradicción
						} else if (role[u.first] == !type) {
							impossible = true;
							break;
						}
					}
				}
				ans += max(imposters, crewmates);
			}
		}
 
		cout << (impossible ? -1 : ans) << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class AmongUs {
	private static class Edge {
		public int first;
		public boolean second;
 
		public Edge(int first, boolean second) {
			this.first = first;
			this.second = second;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		StringBuilder out = new StringBuilder();
		for (int tc = 0; tc < t; tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
 
			// adj[i][j] = {el j-ésimo nodo adyacente desde i
			// su declaración (0 = impostor, 1 = tripulante)}
			List<List<Edge>> adj = new ArrayList<>(n);
			for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
 
			for (int i = 0; i < q; i++) {
				st = new StringTokenizer(br.readLine());
				int type = Integer.parseInt(st.nextToken()) - 1;
				int x = Integer.parseInt(st.nextToken()) - 1;
				int y = Integer.parseInt(st.nextToken()) - 1;
 
				adj.get(x).add(new Edge(y, type != 0));
				adj.get(y).add(new Edge(x, type != 0));
			}
 
			int[] role = new int[n];
			Arrays.fill(role, -1);
 
			int ans = 0;
			boolean impossible = false;
			for (int i = 0; i < n; i++) {
				// aún no visitamos esta componente conexa
				if (role[i] == -1) {
					int imposters = 0, crewmates = 0;
 
					// dfs para construir el grafo bipartito
					Stack<Integer> todo = new Stack<>();
 
					todo.push(i);
					role[i] = 1;
					imposters++;
					while (!todo.isEmpty()) {
						int curr = todo.pop();
 
						for (Edge u : adj.get(curr)) {
							boolean type =
							    u.second ? (role[curr] == 1) : (role[curr] != 1);
 
							// no visitado
							if (role[u.first] == -1) {
								role[u.first] = type ? 1 : 0;
 
								if (type) {
									imposters++;
								} else {
									crewmates++;
								}
 
								todo.push(u.first);
								// crea una contradicción
							} else if (role[u.first] == (type ? 0 : 1)) {
								impossible = true;
								break;
							}
						}
					}
					ans += Math.max(imposters, crewmates);
				}
			}
 
			out.append(impossible ? -1 : ans).append('\n');
		}
 
		System.out.print(out.toString());
	}
}


for _ in range(int(input())):
	n, q = map(int, input().split())
 
	"""
	adj[i][j] = {el j-ésimo nodo adyacente desde i,
	su declaración (0 = impostor, 1 = tripulante)}
	"""
	adj = [[] for _ in range(n)]
 
	for _ in range(q):
		type, x, y = map(int, input().split())
		type -= 1
		x -= 1
		y -= 1
 
		adj[x].append((y, type))
		adj[y].append((x, type))
 
	role = [-1] * n
	ans = 0
	impossible = False
	for i in range(n):
		# aún no visitamos esta componente conexa
		if role[i] == -1:
			imposters = 0
			crewmates = 0
 
			# dfs para construir el grafo bipartito
			todo = [i]
			role[i] = 1
			imposters += 1
 
			while todo:
				curr = todo.pop()
 
				for u in adj[curr]:
					type = role[curr] if u[1] else 1 - role[curr]
 
					# no visitado
					if role[u[0]] == -1:
						role[u[0]] = type
						if type:
							imposters += 1
						else:
							crewmates += 1
 
						todo.append(u[0])
						# crea una contradicción
					elif role[u[0]] != type:
						impossible = True
						break
 
			ans += max(imposters, crewmates)
 
	print(-1 if impossible else ans)