Birthday Party

En este problema nos dan algunas personas que tienen los números de otras, y se nos pregunta si, al perder un par de amigos los números del otro, será imposible invitar a todos.

Generar el grafo

Una vez que hemos desmenuzado el enunciado, podemos aplicar las siguientes definiciones:

Definir a una persona $x$ como un nodo.
Si dos nodos $a$ y $b$ tienen el número del otro, conectarlos con una arista no dirigida.
Se puede invitar a todos a la fiesta si existe exactamente una componente conexa en el grafo.

Ahora el problema pasa a ser: dado un grafo con $p \: (1 \leq p \leq 100)$ nodos y $c \: (0 \leq c \leq 5000)$ aristas, ¿se puede quitar alguna arista para partir el grafo en más de una componente conexa?

Aplicar DFS

Como las cotas de aristas (y de nodos) son pequeñas, podemos ejecutar DFS sobre el grafo. Para cada arista, ejecutemos una DFS asegurándonos de no recorrer esa arista. Si no podemos visitar algún nodo, entonces la respuesta es “YES”. En caso contrario, si podemos visitar todos los nodos para cada arista que se quita, la respuesta es “NO” (nótese que el problema pregunta si es imposible invitar a todos).

Ignorar aristas

La forma más sencilla de ignorar aristas en un grafo es representarlo con una matriz de adyacencia (podemos hacerlo porque la cantidad de nodos es muy pequeña). Para ignorar una arista que conecta dos nodos $a$ y $b$ , basta con poner adj[a][b] y adj[b][a] en false. Más adelante, cuando queramos volver a añadir la arista, podemos actualizar adj[a][b] y adj[b][a] a true.

Implementación

C++Java


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
void setIO(string name = "") {  // name no vacío para E/S por archivos de USACO
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // ver Fast Input & Output
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);  // ver Input & Output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
int n, m;
// Matriz de adyacencia
bool adj[105][105];
bool vis[105];
 
void dfs(int v) {
	vis[v] = true;
	for (int to = 0; to < n; to++) {
		if (adj[v][to] && !vis[to]) { dfs(to); }
	}
}
 
void solve() {
	memset(adj, false, sizeof(adj));
	vector<pi> edges;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u][v] = true;
		adj[v][u] = true;
		edges.pb(mp(u, v));
	}
	for (pi x : edges) {
		adj[x.f][x.s] = false;
		adj[x.s][x.f] = false;
		memset(vis, false, sizeof(vis));
		dfs(0);
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				cout << "Yes" << '\n';
				return;
			}
		}
		adj[x.f][x.s] = true;
		adj[x.s][x.f] = true;
	}
	cout << "No" << '\n';
}
 
int main() {
	setIO();
	while (cin >> n >> m && (n || m)) { solve(); }
}


import java.util.*;
 
public class BirthdayParty {
	static int p, c;
	static boolean[][] adj;
	static boolean[] vis;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		while (true) {
			boolean allConnected = true;
			p = sc.nextInt();
			c = sc.nextInt();
 
			if (p == 0 && c == 0) break;
 
			// Matriz de adyacencia
			adj = new boolean[p][p];
			Edge[] edges = new Edge[c];
			for (int i = 0; i < c; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				adj[a][b] = true;
				adj[b][a] = true;
				edges[i] = new Edge(a, b);
			}
 
			for (Edge edge : edges) {
				// Quitar del grafo la arista que estamos mirando
				adj[edge.a][edge.b] = false;
				adj[edge.b][edge.a] = false;
 
				vis = new boolean[p];
				dfs(0);
 
				for (int i = 0; i < p; i++) {
					// Si un nodo no se visitó después de la dfs, significa que
					// los nodos no están todos en una sola componente conexa
					if (!vis[i]) { allConnected = false; }
				}
 
				// Volver a añadir la arista al grafo
				adj[edge.a][edge.b] = true;
				adj[edge.b][edge.a] = true;
			}
 
			if (allConnected) {
				System.out.println("No");
			} else {
				System.out.println("Yes");
			}
		}
	}
 
	static void dfs(int pos) {
		vis[pos] = true;
		for (int to = 0; to < p; to++) {
			if (adj[pos][to] && !vis[to]) { dfs(to); }
		}
	}
 
	static class Edge {
		int a, b;
 
		Edge(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}
}