Skip to Content
CTRL K

Road Construction

Explicación

Podemos representar el problema como un grafo no dirigido, donde cada una de las nn ciudades es un nodo y cada una de las mm carreteras es una arista. Luego hay dos subproblemas que debemos considerar:

El primer subproblema es contar la cantidad de componentes conexas cada día. Podemos contarlas usando Union-Find / conjuntos disjuntos (DSU), donde cada árbol de la estructura representa una componente conexa. Empezamos con nn ciudades y ninguna carretera entre ellas, y por lo tanto nn componentes conexas. Por cada carretera que se construye, unimos las dos ciudades que conecta. Si la unión es exitosa, entonces dos componentes conexas distintas se juntaron en una, y por lo tanto la cantidad de componentes conexas disminuye en 1.

El segundo subproblema es hallar el tamaño de la componente conexa más grande cada día. Convenientemente, la optimización de unión por tamaño del DSU guarda el tamaño de la componente de cualquier nodo en el nodo padre de ese árbol. Además, la componente más grande solo cambia si una unión es exitosa, porque de lo contrario el grafo se queda igual. Si ocurre una unión, verificamos si el tamaño del árbol al que se agregó durante la unión es un nuevo máximo.

Implementación

Complejidad temporal: O(M⋅α(N))\mathcal{O}(M \cdot \alpha(N))

#include <bits/stdc++.h>
 
using namespace std;
 
struct DSU {
	vector<int> e;
	void init(int n) { e = vector<int>(n, -1); }
	int get(int x) { return (e[x] < 0 ? x : e[x] = get(e[x])); }
	bool sameSet(int x, int y) { return get(x) == get(y); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};
 
int main() {
	int n, m;
	cin >> n >> m;
	DSU dsu;
	dsu.init(n);
	int cc = n, large = 1;
 
	while (m--) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if (dsu.unite(x, y)) {
			large = max(large, dsu.size(x));
			cc--;
		}
		cout << cc << ' ' << large << '\n';
	}
}
import sys
 
input = sys.stdin.readline  # acelerar la entrada para no TLE
 
# BeginCodeSnip{Disjoint Set Union}
class DisjointSetUnion:
	def __init__(self, num_nodes: int) -> None:
		self.parent = [*range(num_nodes)]
		self.size = [1] * num_nodes
 
	def find_parent(self, v: int) -> int:
		if self.parent[v] == v:
			return v
		self.parent[v] = self.find_parent(self.parent[v])
		return self.parent[v]
 
	def union(self, a: int, b: int) -> bool:
		a = self.find_parent(a)
		b = self.find_parent(b)
		if a == b:
			return False
		if self.size[a] < self.size[b]:
			a, b = b, a
		self.parent[b] = a
		self.size[a] += self.size[b]
		return True
 
	def connected(self, a: int, b: int) -> bool:
		return self.find_parent(a) == self.find_parent(b)
 
 
# EndCodeSnip
 
n, m = map(int, input().split())
 
cities = DisjointSetUnion(n)
largest_size = 1
components = n
 
for _ in range(m):
	a, b = map(lambda i: int(i) - 1, input().split())
	if cities.union(a, b):
		components -= 1
 
	# a es el nodo padre al unir en nuestra implementación del dsu
	size_a = cities.size[cities.find_parent(a)]
	if size_a > largest_size:
		largest_size = size_a
 
	print(components, largest_size)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class cses1676 {
	public static int[] disjoint;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		// Inicializar.
		disjoint = new int[N];
		Arrays.fill(disjoint, -1);
		// El tamaño de la componente conexa más grande.
		int largestCC = 1;
 
		// Leer las conexiones.
		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int newSize = union(a, b);
			if (newSize != 0) {
				N--;
				// Verificar cuál componente conexa es más grande.
				largestCC = Integer.max(largestCC, newSize);
			}
			pw.println(N + " " + largestCC);
		}
		pw.close();
	}
 
	/*Union-Find / conjuntos disjuntos */
 
	// Hallar el ancestro.
	public static int find(int v) {
		if (disjoint[v] < 0) { return v; }
		disjoint[v] = find(disjoint[v]);
		return disjoint[v];
	}
 
	public static int union(int u, int v) {
		// Hallar el ancestro de ambos nodos
		u = find(u);
		v = find(v);
 
		// Están en la misma componente conexa.
		if (u == v) { return 0; }
 
		if (disjoint[u] < disjoint[v]) {
			int tempU = u;
			u = v;
			v = tempU;
		}
		disjoint[v] += disjoint[u];  // Agregar los hijos de u a v.
		disjoint[u] = v;             // Poner a v como padre de u.
		return -disjoint[v];
	}
}
Fundamentos