Skip to Content
CTRL K

Closing the Farm

Análisis oficial (C++) 

En este problema, se nos pide determinar si todos los graneros restantes están conectados a medida que los graneros se cierran de a uno. Para comprobarlo, podemos ejecutar una búsqueda en profundidad (DFS) empezando desde el granero que se cerrará último. Para simular el cierre de cada granero, podemos guardar un arreglo booleano y marcar cada granero de la iteración como “cerrado”. Luego, podemos ejecutar el DFS y comprobar cuántos nodos se visitaron. Si se visitaron todos los nodos no cerrados, imprimimos “YES”; si no, imprimimos “NO”.

Implementación

Complejidad temporal: O(N2+NM)\mathcal{O}(N^2 + NM)

import sys
 
sys.stdin = open("closing.in", "r")
sys.stdout = open("closing.out", "w")
 
n, m = map(int, input().split())
 
adj, order = {}, []
for i in range(1, n + 1):
	adj[i] = []
 
visited, closed = [False] * (n + 1), [False] * (n + 1)
nodes = 0
 
 
def dfs(node):
	global nodes
	if visited[node] or closed[node]:
		return
 
	# Visitamos este nodo si no está cerrado y aún no lo visitamos.
	nodes += 1
	visited[node] = True
 
	for u in adj[node]:
		if not visited[u]:
			dfs(u)
 
 
# Leemos la lista de adyacencia.
for i in range(m):
	a, b = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
 
for i in range(n):
	order.append(int(input()))
 
dfs(1)
 
"""
La granja está inicialmente conexa si visitamos todos los nodos
antes de que se cierre cualquiera de los graneros.
"""
print("YES") if nodes == n else print("NO")
 
for i in range(n - 1):
	visited = [False] * (n + 1)
	nodes = 0
	closed[order[i]] = True
 
	# Empezamos DFS desde el granero que se cerrará último.
	dfs(order[n - 1])
 
	# ¿Visitamos todos los graneros no cerrados?
	if nodes == n - i - 1:
		print("YES")
	else:
		print("NO")
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
const int MAX_N = 3000;
 
vector<vector<int>> adj(MAX_N);
vector<int> vis(MAX_N);
vector<int> closed(MAX_N);
int nodes = 0;
 
void dfs(int node) {
	if (vis[node] || closed[node]) return;
 
	// Visitamos este nodo si no está cerrado y aún no lo visitamos.
	nodes++;
	vis[node] = true;
 
	for (int u : adj[node]) {
		if (!vis[u]) dfs(u);
	}
}
 
int main() {
	freopen("closing.in", "r", stdin);
	freopen("closing.out", "w", stdout);
 
	cin >> n >> m;
 
	// Leemos la lista de adyacencia.
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	vector<int> ord(n);
	for (int i = 0; i < n; i++) cin >> ord[i];
 
	dfs(1);
 
	/*
	 * La granja está inicialmente conexa si visitamos todos los nodos
	 * antes de que se cierre cualquiera de los graneros.
	 */
	if (nodes == n) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
 
	for (int i = 0; i < n - 1; i++) {
		nodes = 0;
		closed[ord[i]] = true;
		fill(vis.begin(), vis.end(), false);
 
		// Empezamos DFS desde el granero que se cerrará último.
		dfs(ord[n - 1]);
 
		// ¿Visitamos todos los graneros no cerrados?
		if (nodes == n - i - 1) {
			cout << "YES" << "\n";
		} else {
			cout << "NO" << "\n";
		}
	}
}
import java.io.*;
import java.util.*;
 
public class closing {
	// Variables globales usadas por dfs
	static ArrayList<ArrayList<Integer>> adj;
	static boolean[] visited, closed;
	static int nodes;
 
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("closing.in"));
		PrintWriter out = new PrintWriter("closing.out");
 
		int n = sc.nextInt();
		int m = sc.nextInt();
 
		visited = new boolean[n];
		closed = new boolean[n];
		adj = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < n; i++) adj.add(new ArrayList<Integer>());
 
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		int[] order = new int[n];
		for (int i = 0; i < n; i++) { order[i] = sc.nextInt() - 1; }
 
		for (int i = 0; i < n; i++) {
			Arrays.fill(visited, false);
			nodes = 0;
 
			dfs(order[n - 1]);  // DFS desde el granero que se cerrará último
			// Comprueba si se visitaron todos los graneros no cerrados
			if (nodes == n - i) {
				out.println("YES");
			} else {
				out.println("NO");
			}
			closed[order[i]] = true;
		}
		out.close();
	}
 
	static void dfs(int node) {
		if (visited[node] || closed[node]) return;
 
		// Aumentamos el número de nodos
		// iff este granero no está ya cerrado o visitado
		nodes++;
		visited[node] = true;
		for (int neighbor : adj.get(node)) { dfs(neighbor); }
	}
}
Fundamentos