Milk Factory

Pistas

Pista 1

¿Qué propiedades podemos deducir sobre esta supuesta estación $i$ que nos ayuden a encontrarla?

Pista 2

Dadas las pasarelas de un solo sentido, si podemos llegar a la estación $a$ desde la estación $b$ , ¿significa eso que podemos llegar a la estación $b$ desde la estación $a$ ?

Pista 3

La respuesta a la pregunta de la pista anterior debería ser “No”. Sabemos que toda estación puede llegar a la estación $i$ ; ¿qué implica esto sobre las pasarelas conectadas a la estación $i$ (como inicio o como fin)?

Solución 1

Explicación

Observemos que la estructura con la que tratamos acá es un árbol, o un conjunto de $N$ nodos conectados por $N - 1$ aristas donde todo nodo es alcanzable desde cualquier otro y no existen ciclos.

Llamemos “sumidero” (sink) a un nodo que solo tiene aristas dirigidas entrantes. Ahora afirmamos que existe un sumidero $X$ en nuestro árbol si y solo si todos los demás nodos pueden alcanzar $X$ . Además, si $X$ existe, es el único sumidero. Intentemos ver por qué es cierto antes de continuar.

Demostración

Si todos los nodos del árbol pueden alcanzar algún nodo $X$ , entonces $X$ debe ser un sumidero. Además, $X$ debe ser el único sumidero, ya que todos los demás nodos necesitan al menos una arista dirigida saliente para poder salir de ellos, así que no son sumideros. $X$ no puede tener aristas salientes, porque si hubiera una arista que conecta $X$ con el nodo $Y$ , entonces $Y$ no podría alcanzar $X$ .
Si $X$ es el único sumidero, entonces todos los nodos del árbol pueden alcanzar $X$ . Supongamos que algún nodo $Y$ no puede alcanzar $X$ . Sabemos que $Y$ tiene una arista saliente porque no es un sumidero, así que seguimos esa arista. Entonces el nodo al que llegamos también tiene una arista saliente porque no es un sumidero, y seguir repetidamente estas aristas nos llevará inevitablemente a un sumidero. Como $X$ es el único sumidero, debemos haber llegado a $X$ .

Por lo tanto, podemos llevar registro de la cantidad de aristas salientes de cada nodo, y si hay exactamente un sumidero $X$ , entonces $X$ es nuestra respuesta.

Implementación

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

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("factory.in");
	int station_num;
	read >> station_num;
 
	vector<int> outgoing(station_num);
	for (int w = 0; w < station_num - 1; w++) {
		int s1, s2;
		read >> s1 >> s2;
		// En realidad no nos importa s2 acá.
		outgoing[--s1]++;
	}
 
	vector<int> no_outs;
	// Revisamos todas las estaciones y vemos si no tienen pasarelas salientes
	for (int s = 0; s < station_num; s++) {
		if (outgoing[s] == 0) {
			// Recordemos que hay que imprimir las estaciones con indexación desde uno.
			no_outs.push_back(s + 1);
		}
	}
 
	// Si hay dos estaciones sin salidas, entonces no podemos encontrar una estación
	int root = no_outs.size() == 1 ? no_outs[0] : -1;
	std::ofstream("factory.out") << root << endl;
}


import java.io.*;
import java.util.*;
 
public class Factory {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("factory.in"));
		int stationNum = Integer.parseInt(read.readLine());
		int[] outgoing = new int[stationNum];
		for (int w = 0; w < stationNum - 1; w++) {
			StringTokenizer walkway = new StringTokenizer(read.readLine());
			int s1 = Integer.parseInt(walkway.nextToken()) - 1;
			// En realidad no nos importa s2 acá.
			outgoing[s1]++;
		}
		read.close();
 
		// Revisamos todas las estaciones y vemos si no tienen pasarelas salientes
		List<Integer> noOuts = new ArrayList<>();
		for (int s = 0; s < stationNum; s++) {
			if (outgoing[s] == 0) {
				// Recordemos que hay que imprimir las estaciones con indexación desde uno.
				noOuts.add(s + 1);
			}
		}
 
		// Si hay dos estaciones sin salidas, entonces no podemos encontrar una
		// estación
		int root = noOuts.size() == 1 ? noOuts.get(0) : -1;
 
		PrintWriter written = new PrintWriter("factory.out");
		written.println(root);
		written.close();
	}
}


with open("factory.in") as read:
	station_num = int(read.readline())
	outgoing = [0 for _ in range(station_num)]
	for _ in range(station_num - 1):
		s1, s2 = [int(i) - 1 for i in read.readline().split()]
		# En realidad no nos importa s2 acá.
		outgoing[s1] += 1
 
no_outs = []
# Revisamos todas las estaciones y vemos si no tienen pasarelas salientes
for s in range(station_num):
	if outgoing[s] == 0:
		# Recordemos que hay que imprimir las estaciones con indexación desde uno.
		no_outs.append(s + 1)
 
# Si hay dos estaciones sin salidas, entonces no podemos encontrar una estación
root = no_outs[0] if len(no_outs) == 1 else -1
print(root, file=open("factory.out", "w"))

Solución 2

Explicación

Este problema también se puede resolver usando DFS (un tema de Plata). Podemos representar la fábrica como un grafo dirigido no ponderado con aristas de $b_i$ a $a_i$ para todo $i$ . Para cada nodo $i\in [1,N]$ , empezamos un DFS en el nodo $i$ y comprobamos si esto resulta en que se visiten todos los demás nodos. Podemos llevar registro de si el DFS actual visita todos los nodos con un arreglo booleano cuyas entradas se inicializan en false. Si se visita cada nodo, entonces imprimimos $i$ . En caso contrario, si no existe ningún $i$ tal que se cumpla esta condición, entonces imprimimos $-1$ .

Implementación

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

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("factory.in");
	int station_num;
	read >> station_num;
 
	vector<vector<int>> neighbors(station_num);
	for (int w = 0; w < station_num - 1; w++) {
		int s1, s2;
		read >> s1 >> s2;
		neighbors[--s2].push_back(--s1);
	}
 
	// La estación a la que todas las demás deberían poder llegar
	int root = -1;
	// Revisamos todas las estaciones y vemos si pueden ser la raíz
	for (int s = 0; s < station_num; s++) {
		vector<bool> visited(station_num);
		// Siempre podemos llegar a una estación desde sí misma
		visited[s] = true;
 
		// Nuestra pila para DFS
		vector<int> todo{s};
		while (!todo.empty()) {
			int curr = todo.back();
			todo.pop_back();
			for (int n : neighbors[curr]) {
				// Nos aseguramos de visitar solo nodos no visitados
				if (!visited[n]) {
					visited[n] = true;
					todo.push_back(n);
				}
			}
		}
 
		// Comprobamos si se visitaron todos los nodos
		bool valid = true;
		for (int check_s = 0; check_s < station_num; check_s++) {
			if (!visited[check_s]) {
				valid = false;
				break;
			}
		}
 
		if (valid) {
			root = s + 1;
			break;
		}
	}
 
	std::ofstream("factory.out") << root << endl;
}


import java.io.*;
import java.util.*;
 
public class Factory {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("factory.in"));
		int stationNum = Integer.parseInt(read.readLine());
 
		List<Integer>[] neighbors = new ArrayList[stationNum];
		for (int s = 0; s < stationNum; s++) { neighbors[s] = new ArrayList<>(); }
		for (int w = 0; w < stationNum - 1; w++) {
			StringTokenizer walkway = new StringTokenizer(read.readLine());
			int s1 = Integer.parseInt(walkway.nextToken()) - 1;
			int s2 = Integer.parseInt(walkway.nextToken()) - 1;
			neighbors[s2].add(s1);
		}
		read.close();
 
		// La estación a la que todas las demás deberían poder llegar
		int root = -1;
		// Revisamos todas las estaciones y vemos si pueden ser la raíz
		for (int s = 0; s < stationNum; s++) {
			boolean[] visited = new boolean[stationNum];
			// Siempre podemos llegar a una estación desde sí misma
			visited[s] = true;
 
			// Nuestra pila para DFS
			List<Integer> todo = new ArrayList<>(Collections.singletonList(s));
			while (!todo.isEmpty()) {
				int curr = todo.remove(todo.size() - 1);
				for (int n : neighbors[curr]) {
					// Nos aseguramos de visitar solo nodos no visitados
					if (!visited[n]) {
						visited[n] = true;
						todo.add(n);
					}
				}
			}
 
			// Comprobamos si se visitaron todos los nodos
			boolean valid = true;
			for (int checkS = 0; checkS < stationNum; checkS++) {
				if (!visited[checkS]) {
					valid = false;
					break;
				}
			}
 
			if (valid) {
				root = s + 1;
				break;
			}
		}
 
		PrintWriter written = new PrintWriter("factory.out");
		written.println(root);
		written.close();
	}
}


with open("factory.in") as read:
	station_num = int(read.readline())
	neighbors = [[] for _ in range(station_num)]
	for _ in range(station_num - 1):
		s1, s2 = [int(i) - 1 for i in read.readline().split()]
		neighbors[s2].append(s1)
 
# La estación a la que todas las demás deberían poder llegar
root = -1
# Revisamos todas las estaciones y vemos si pueden ser la raíz
for s in range(station_num):
	visited = [False for _ in range(station_num)]
	# Siempre podemos llegar a una estación desde sí misma
	visited[s] = True
 
	# Nuestra pila para DFS
	todo = [s]
	while todo:
		curr = todo.pop()
		for n in neighbors[curr]:
			# Nos aseguramos de visitar solo nodos no visitados
			if not visited[n]:
				visited[n] = True
				todo.append(n)
 
	# Comprobamos si se visitaron todos los nodos
	if all(visited):
		root = s + 1
		break
 
print(root, file=open("factory.out", "w"))

Solución en video

Por Neo Wang

Video de YouTube (fN681Y5TEQc)

Código de la solución en video

C++Java


#include <bits/stdc++.h>  // ver /general/running-code-locally
using namespace std;
 
using ll = long long;
 
using vi = vector<int>;
#define pb push_back
#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 = "") {
	cin.tie(0)->sync_with_stdio(0);  // ver /general/fast-io
	if (sz(name)) {
		(void)!freopen((name + ".in").c_str(), "r", stdin);  // ver /general/io
		(void)!freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
int in_deg[101], out_deg[101];
 
int main() {
	setIO("factory");
 
	int N;
	cin >> N;
 
	// N - 1 aristas en un árbol
	for (int i = 0; i < N - 1; i++) {
		// a -> b
		// out[a]++, in[b]++;
		int a, b;
		cin >> a >> b;
		out_deg[a]++;
		in_deg[b]++;
	}
 
	bool encountered_sink = false;
	int idx_sink = -1;
 
	for (int i = 1; i <= N; i++) {
		if (encountered_sink && out_deg[i] == 0 && in_deg[i] > 0) {
			idx_sink = -1;  // respuesta
			break;
		}
		if (out_deg[i] == 0 && in_deg[i] > 0) {
			encountered_sink = true;
			idx_sink = i;
		}
	}
 
	cout << idx_sink << endl;
}


import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("factory");
		int N = io.nextInt();
		int[] in_deg = new int[101], out_deg = new int[101];
		for (int i = 0; i < N - 1; i++) {
			// a -> b
			// out[a]++, in[b]++;
			int a = io.nextInt(), b = io.nextInt();
			out_deg[a]++;
			in_deg[b]++;
		}
 
		boolean encountered_sink = false;
		int idx_sink = -1;
 
		for (int i = 1; i <= N; i++) {
			if (encountered_sink && out_deg[i] == 0 && in_deg[i] > 0) {
				idx_sink = -1;
				break;
			}
 
			if (out_deg[i] == 0 && in_deg[i] > 0) {
				encountered_sink = true;
				idx_sink = i;
			}
		}
 
		// cout << idx_sink << endl;
		io.println(idx_sink);
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}