Wormhole Sort

Solución 1 - Búsqueda binaria y flood fill

Si un cierto ancho de agujero de gusano funciona, cualquier ancho menor también funcionará. De forma similar, si un ancho falla, cualquier ancho mayor también fallará. Estos dos hechos hacen que podamos hacer búsqueda binaria sobre el ancho mínimo de agujero de gusano.

Para comprobar si un ancho mínimo de agujero de gusano $x$ es válido, usamos DFS para hallar todas las posiciones que pueden alcanzarse entre sí recorriendo agujeros de gusano de ancho a lo sumo $x$ . Si la posición inicial de la vaca y su posición ordenada están ambas en la misma componente, ¡encontramos un ancho de agujero de gusano válido!

Por ejemplo, digamos que estamos probando un ancho de $10$ en el caso de ejemplo. Esto hace que nuestras componentes sean $[0]$ , $[1, 2]$ y $[3]$ . La posición inicial de la vaca 1 (3) y su posición final (0) no están en la misma componente, así que este ancho no funcionaría.

Implementación

Complejidad temporal: $\mathcal O((N+M)\log \max w_i)$

C++Java


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("wormsort.in");
	int cow_num;
	int wormhole_num;
	read >> cow_num >> wormhole_num;
 
	vector<int> cows(cow_num);
	for (int &c : cows) {
		read >> c;
		c--;  // hacemos las vacas indexadas desde 0
	}
 
	int max_width = 0;
	vector<vector<std::pair<int, int>>> neighbors(cow_num);
	for (int w = 0; w < wormhole_num; w++) {
		int c1, c2, width;
		read >> c1 >> c2 >> width;
		c1--;
		c2--;
		neighbors[c1].push_back({c2, width});
		neighbors[c2].push_back({c1, width});
		max_width = std::max(max_width, width);
	}
 
	int lo = 0;
	int hi = max_width + 1;
	int valid = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
 
		vector<int> component(cow_num, -1);
		int curr_comp = 0;
		for (int c = 0; c < cow_num; c++) {
			if (component[c] != -1) { continue; }
			vector<int> frontier{c};
			while (!frontier.empty()) {
				int curr = frontier.back();
				frontier.pop_back();
				component[curr] = curr_comp;
				for (const auto &[n, w] : neighbors[curr]) {
					if (component[n] == -1 && w >= mid) { frontier.push_back(n); }
				}
			}
			curr_comp++;
		}
 
		bool sortable = true;
		for (int c = 0; c < cow_num; c++) {
			if (component[c] != component[cows[c]]) {
				sortable = false;
				break;
			}
		}
 
		if (sortable) {
			valid = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
 
	std::ofstream("wormsort.out") << (valid == max_width + 1 ? -1 : valid) << endl;
}


import java.io.*;
import java.util.*;
 
public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");
 
		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();
 
		int[] cows = new int[cowNum];
		for (int c = 0; c < cowNum; c++) { cows[c] = io.nextInt() - 1; }
 
		int maxWidth = 0;
		List<int[]>[] neighbors = new ArrayList[cowNum];
		for (int c = 0; c < cowNum; c++) { neighbors[c] = new ArrayList<>(); }
		for (int w = 0; w < wormholeNum; w++) {
			int c1 = io.nextInt() - 1;
			int c2 = io.nextInt() - 1;
			int width = io.nextInt();
			neighbors[c1].add(new int[] {c2, width});
			neighbors[c2].add(new int[] {c1, width});
			maxWidth = Math.max(maxWidth, width);
		}
 
		int lo = 0;
		int hi = maxWidth + 1;
		int valid = -1;
		int[] component = new int[cowNum];
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
 
			Arrays.fill(component, -1);
			int currComp = 0;
			for (int c = 0; c < cowNum; c++) {
				if (component[c] != -1) { continue; }
				List<Integer> frontier = new ArrayList<>(Collections.singletonList(c));
				while (!frontier.isEmpty()) {
					int curr = frontier.remove(frontier.size() - 1);
					component[curr] = currComp;
					for (int[] n : neighbors[curr]) {
						if (component[n[0]] == -1 && n[1] >= mid) {
							frontier.add(n[0]);
						}
					}
				}
				currComp++;
			}
 
			boolean sortable = true;
			for (int c = 0; c < cowNum; c++) {
				if (component[c] != component[cows[c]]) {
					sortable = false;
					break;
				}
			}
 
			if (sortable) {
				valid = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
 
		io.println(valid == maxWidth + 1 ? -1 : valid);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Solución 2 - Búsqueda binaria y DSU

Como en la solución de flood fill, hacemos búsqueda binaria sobre la respuesta $x$ , que es válida si todos los $p_i$ están en la misma componente que $i$ , lo cual podemos consultar en $\mathcal{O}(\alpha(N))$ usando un Union-Find / conjuntos disjuntos (DSU).

Implementación

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

C++Java


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{DSU}
class DSU {
  private:
	vector<int> parent;
	vector<int> size;
 
  public:
	DSU(int size) : parent(size), size(size, 1) {
		for (int i = 0; i < size; i++) { parent[i] = i; }
	}
 
	int get_top(int n) { return parent[n] == n ? n : (parent[n] = get_top(parent[n])); }
 
	bool link(int n1, int n2) {
		n1 = get_top(n1);
		n2 = get_top(n2);
		if (n1 == n2) { return false; }
		if (size[n2] > size[n1]) { return link(n2, n1); }
		parent[n2] = n1;
		size[n1] += size[n2];
		return true;
	}
};
// EndCodeSnip
 
struct Wormhole {
	int c1, c2;
	int width;
};
 
int main() {
	std::ifstream read("wormsort.in");
	int cow_num;
	int wormhole_num;
	read >> cow_num >> wormhole_num;
 
	vector<int> cows(cow_num);
	for (int &c : cows) {
		read >> c;
		c--;  // hacemos las vacas indexadas desde 0
	}
 
	int max_width = 0;
	vector<Wormhole> wormholes(wormhole_num);
	for (Wormhole &w : wormholes) {
		read >> w.c1 >> w.c2 >> w.width;
		w.c1--;
		w.c2--;
		max_width = std::max(max_width, w.width);
	}
 
	int lo = 0;
	int hi = max_width + 1;
	int valid = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
 
		DSU dsu(cow_num);
		for (const Wormhole &w : wormholes) {
			if (w.width >= mid) { dsu.link(w.c1, w.c2); }
		}
 
		bool sortable = true;
		for (int c = 0; c < cow_num; c++) {
			if (dsu.get_top(c) != dsu.get_top(cows[c])) {
				sortable = false;
				break;
			}
		}
 
		if (sortable) {
			valid = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
 
	std::ofstream("wormsort.out") << (valid == max_width + 1 ? -1 : valid) << endl;
}


import java.io.*;
import java.util.*;
 
public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");
 
		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();
 
		int[] cows = new int[cowNum];
		for (int c = 0; c < cowNum; c++) { cows[c] = io.nextInt() - 1; }
 
		int maxWidth = 0;
		List<int[]> wormholes = new ArrayList<>();
		for (int w = 0; w < wormholeNum; w++) {
			wormholes.add(new int[] {io.nextInt() - 1, io.nextInt() - 1, io.nextInt()});
			maxWidth = Math.max(maxWidth, wormholes.get(w)[2]);
		}
 
		int lo = 0;
		int hi = maxWidth + 1;
		int valid = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
 
			DSU dsu = new DSU(cowNum);
			for (int[] w : wormholes) {
				if (w[2] >= mid) { dsu.link(w[0], w[1]); }
			}
 
			boolean sortable = true;
			for (int c = 0; c < cowNum; c++) {
				if (dsu.getTop(c) != dsu.getTop(cows[c])) {
					sortable = false;
					break;
				}
			}
 
			if (sortable) {
				valid = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
 
		io.println(valid == maxWidth + 1 ? -1 : valid);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
 
// BeginCodeSnip{DSU}
class DSU {
	private final int[] parent;
	private final int[] size;
	public DSU(int size) {
		parent = new int[size];
		this.size = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			this.size[i] = 1;
		}
	}
 
	public int getTop(int n) {
		return parent[n] == n ? n : (parent[n] = getTop(parent[n]));
	}
 
	public boolean link(int e1, int e2) {
		e1 = getTop(e1);
		e2 = getTop(e2);
		if (e1 == e2) { return false; }
		if (size[e2] > size[e1]) { return link(e2, e1); }
		parent[e2] = e1;
		size[e1] += size[e2];
		return true;
	}
}
// EndCodeSnip

Solución 3 - DSU

Debido a la complejidad rápida de consulta y unión del DSU, podemos dejar de lado la búsqueda binaria y en cambio agregar agujeros de gusano del mayor ancho al menor hasta que todos los $p_i$ estén en la misma componente que $i$ .

Implementación

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

C++Java


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{DSU}
class DSU {
  private:
	vector<int> parent;
	vector<int> size;
 
  public:
	DSU(int size) : parent(size), size(size, 1) {
		for (int i = 0; i < size; i++) { parent[i] = i; }
	}
 
	int get_top(int n) { return parent[n] == n ? n : (parent[n] = get_top(parent[n])); }
 
	bool link(int n1, int n2) {
		n1 = get_top(n1);
		n2 = get_top(n2);
		if (n1 == n2) { return false; }
		if (size[n2] > size[n1]) { return link(n2, n1); }
		parent[n2] = n1;
		size[n1] += size[n2];
		return true;
	}
};
// EndCodeSnip
 
struct Wormhole {
	int c1, c2;
	int width;
};
 
bool operator<(const Wormhole &w1, const Wormhole &w2) { return w1.width < w2.width; }
 
int main() {
	std::ifstream read("wormsort.in");
	int cow_num;
	int wormhole_num;
	read >> cow_num >> wormhole_num;
 
	vector<int> cows(cow_num);
	for (int &c : cows) {
		read >> c;
		c--;  // hacemos las vacas indexadas desde 0
	}
 
	vector<Wormhole> wormholes(wormhole_num);
	for (Wormhole &w : wormholes) {
		read >> w.c1 >> w.c2 >> w.width;
		w.c1--;
		w.c2--;
	}
 
	std::sort(wormholes.begin(), wormholes.end());
 
	int wormhole_at = wormhole_num;
	DSU dsu(cow_num);
	for (int i = 0; i < cow_num; i++) {
		while (dsu.get_top(i) != dsu.get_top(cows[i])) {
			wormhole_at--;
			dsu.link(wormholes[wormhole_at].c1, wormholes[wormhole_at].c2);
		}
	}
 
	std::ofstream("wormsort.out")
	    << (wormhole_at == wormhole_num ? -1 : wormholes[wormhole_at].width) << endl;
}


import java.io.*;
import java.util.*;
 
public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");
 
		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();
 
		int[] cows = new int[cowNum];
		for (int c = 0; c < cowNum; c++) { cows[c] = io.nextInt() - 1; }
 
		int maxWidth = 0;
		List<int[]> wormholes = new ArrayList<>();
		for (int w = 0; w < wormholeNum; w++) {
			wormholes.add(new int[] {io.nextInt() - 1, io.nextInt() - 1, io.nextInt()});
			maxWidth = Math.max(maxWidth, wormholes.get(w)[2]);
		}
 
		wormholes.sort(Comparator.comparingInt(wh -> wh[2]));
 
		int wormholeAt = wormholeNum;
		DSU dsu = new DSU(cowNum);
		for (int i = 0; i < cowNum; i++) {
			while (dsu.getTop(i) != dsu.getTop(cows[i])) {
				wormholeAt--;
				dsu.link(wormholes.get(wormholeAt)[0], wormholes.get(wormholeAt)[1]);
			}
		}
 
		io.println(wormholeAt == wormholeNum ? -1 : wormholes.get(wormholeAt)[2]);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
 
// BeginCodeSnip{DSU}
class DSU {
	private final int[] parent;
	private final int[] size;
	public DSU(int size) {
		parent = new int[size];
		this.size = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			this.size[i] = 1;
		}
	}
 
	public int getTop(int n) {
		return parent[n] == n ? n : (parent[n] = getTop(parent[n]));
	}
 
	public boolean link(int e1, int e2) {
		e1 = getTop(e1);
		e2 = getTop(e2);
		if (e1 == e2) { return false; }
		if (size[e2] > size[e1]) { return link(e2, e1); }
		parent[e2] = e1;
		size[e1] += size[e2];
		return true;
	}
}
// EndCodeSnip