Connecting Two Barns

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;
		cin >> n >> m;
 
		vector<vector<int>> adj(n);
		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;
			adj[--u].push_back(--v);
			adj[v].push_back(u);
		}
 
		// vis[i] guarda la etiqueta de componente del nodo i
		vector<int> vis(n, -1);
		int num_components = 0;
 
		// Identificar componentes conexas usando DFS
		for (int i = 0; i < n; i++) {
			if (vis[i] != -1) { continue; }
			// DFS usando una pila
			stack<int> s;
			s.push(i);
			while (!s.empty()) {
				int u = s.top();
				s.pop();
				if (vis[u] != -1) { continue; }
				vis[u] = num_components;
				for (ll v : adj[u]) {
					if (vis[v] == -1) { s.push(v); }
				}
			}
			num_components++;
		}
 
		// components[i] guarda todos los nodos con etiqueta de componente i
		vector<vector<int>> components(num_components);
		for (int i = 0; i < n; i++) { components[vis[i]].push_back(i); }
 
		// Componentes que contienen el establo inicial (0) y el final (n-1)
		vector<int> start_component = components[vis[0]];
		vector<int> end_component = components[vis[n - 1]];
 
		// Inicializar vectores de distancia con infinito
		vector<int> dist1(num_components, INT_MAX);
		vector<int> dist2(num_components, INT_MAX);
 
		// Calcular distancias mínimas a start_component
		int a = 0;
		for (int i = 0; i < n; i++) {
			int dist = abs(start_component[a] - i);
			while (a < start_component.size() - 1 &&
			       abs(start_component[a + 1] - i) < dist) {
				a++;
			}
			dist1[vis[i]] = min(dist1[vis[i]], dist);
		}
 
		// Calcular distancias mínimas a end_component
		int b = 0;
		for (int i = 0; i < n; i++) {
			int dist = abs(end_component[b] - i);
			while (b < end_component.size() - 1 &&
			       abs(end_component[b + 1] - i) < dist) {
				b++;
			}
			dist2[vis[i]] = min(dist2[vis[i]], dist);
		}
 
		// Calcular el resultado hallando la suma mínima de distancias al cuadrado
		ll res = LLONG_MAX;
		for (int i = 0; i < num_components; i++) {
			res = min(res, 1LL * dist1[i] * dist1[i] + 1LL * dist2[i] * dist2[i]);
		}
		cout << res << '\n';
	}
}

import java.io.*;
import java.util.*;
 
public class ConnectingTwoBarns {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int t = io.nextInt();
		for (int test = 0; test < t; test++) {
			int n = io.nextInt();
			int m = io.nextInt();
 
			List<List<Integer>> adj = new ArrayList<>();
			for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); }
			for (int i = 0; i < m; i++) {
				int a = io.nextInt() - 1;
				int b = io.nextInt() - 1;
				adj.get(a).add(b);
				adj.get(b).add(a);
			}
 
			// guarda el componente de cada nodo
			int[] visited = new int[n];
 
			int numComponents = 0;
			Arrays.fill(visited, -1);
			for (int i = 0; i < n; i++) {
				// ejecutar DFS en el nodo si no ha sido visitado
				if (visited[i] == -1) {
					Stack<Integer> stack = new Stack<>();
					stack.push(i);
					while (!stack.isEmpty()) {
						int curr = stack.pop();
						if (visited[curr] != -1) continue;
 
						// marcar el nodo como visitado
						visited[curr] = numComponents;
 
						for (int neighbor : adj.get(curr)) { stack.push(neighbor); }
					}
					numComponents++;
				}
			}
 
			// guarda una lista de nodos para cada componente
			List<List<Integer>> components = new ArrayList<>();
			for (int i = 0; i < numComponents; i++) {
				components.add(new ArrayList<>());
			}
			/*
			 * añadir cada campo a su componente conexa; como iteramos
			 * de 0...n-1, cada componente está garantizado en orden
			 * ordenado
			 */
			for (int i = 0; i < n; i++) { components.get(visited[i]).add(i); }
 
			// los componentes que contienen los dos establos
			List<Integer> barn1 = components.get(visited[0]);
			List<Integer> barn2 = components.get(visited[n - 1]);
			// dist mínima entre cada componente intermedia y los dos establos
			long[] dist1 = new long[numComponents];
			long[] dist2 = new long[numComponents];
			Arrays.fill(dist1, Integer.MAX_VALUE);
			Arrays.fill(dist2, Integer.MAX_VALUE);
 
			// usar dos punteros para llenar dist1
			int barn1Index = 0;
			for (int i = 0; i < n; i++) {
				int dist = Math.abs(barn1.get(barn1Index) - i);
 
				/*
				 * si la distancia entre i y el campo actual del
				 * componente de barn1 es mayor que la distancia entre i
				 * y el siguiente campo del componente de barn1,
				 * incrementamos barn1Index hasta que esto deje de
				 * cumplirse
				 */
				while (
				    // asegurarnos de no salirnos de los límites
				    barn1Index < barn1.size() - 1 &&
				    Math.abs(barn1.get(barn1Index + 1) - i) < dist) {
					barn1Index++;
				}
 
				/*
				 * ahora encontramos el campo del componente del establo 1
				 * más cercano a i
				 *
				 * podemos usarlo para actualizar la distancia mínima entre
				 * el componente del campo i y el del establo 1
				 */
				dist1[visited[i]] = Math.min(dist, dist1[visited[i]]);
			}
 
			// usar dos punteros para llenar dist2
			int barn2Index = 0;
			for (int i = 0; i < n; i++) {
				int dist = Math.abs(barn2.get(barn2Index) - i);
 
				while (barn2Index < barn2.size() - 1 &&
				       Math.abs(barn2.get(barn2Index + 1) - i) < dist) {
					barn2Index++;
				}
				dist2[visited[i]] = Math.min(dist, dist2[visited[i]]);
			}
 
			// calcular el costo mínimo
			long min = Long.MAX_VALUE;
			for (int i = 0; i < numComponents; i++) {
				long cost = dist1[i] * dist1[i] + dist2[i] * dist2[i];
				min = Math.min(min, cost);
			}
			io.println(min);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int MAX_N = 1e5;
 
vector<int> adj[MAX_N];
// Lista de todos los componentes de la granja
vector<int> comps[MAX_N];
// Dado un nodo, devuelve el índice del componente al que pertenece
int comp[MAX_N];
 
// DFS para hallar las componentes conexas
void dfs(int cur, int c) {
	if (comp[cur] != -1) { return; }
	comp[cur] = c;
	for (int u : adj[cur]) { dfs(u, c); }
}
 
ll cost(int a, int b) {
	int dist = MAX_N;
	for (int u : comps[a]) {
		/*
		 * Hallar el campo más cercano del componente conexo
		 * de b al campo u y actualizar la distancia
		 * mínima. El campo más cercano se halla con
		 * búsqueda binaria sobre un arreglo ordenado
		 * (el componente conexo de b).
		 */
		int i = lower_bound(comps[b].begin(), comps[b].end(), u) - comps[b].begin();
		if (i > 0) { dist = min(dist, abs(comps[b][i - 1] - u)); }
		if (i < comps[b].size()) { dist = min(dist, abs(comps[b][i] - u)); }
	}
	/*
	 * Devuelve el costo mínimo de construir un camino
	 * entre los dos componentes (o sea dist^2)
	 */
	return (ll)dist * dist;
}
 
void solve() {
	int n, m;
	cin >> n >> m;
 
	// Reiniciar nuestras variables para cada caso de prueba
	for (int i = 0; i < n; i++) {
		comp[i] = -1;
		adj[i].clear();
		comps[i].clear();
	}
 
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	/*
	 * Guarda la cantidad de componentes conexas
	 * (se inicia en -1 para no sobrecontar)
	 */
	int cur = -1;
	// Usa DFS para hallar cada componente conexa
	for (int i = 0; i < n; i++) {
		if (comp[i] == -1) { dfs(i, ++cur); }
	}
 
	/*
	 * Añadir cada campo a su componente conexa.
	 * Como iteramos de 0...n-1, cada
	 * componente conexa está garantizada en
	 * orden ordenado
	 */
	for (int i = 0; i < n; i++) { comps[comp[i]].push_back(i); }
 
	/*
	 * La respuesta inicial se pone como el costo de construir
	 * un camino directo entre los campos 1 y N. Esto también
	 * cubre el caso en que los campos 1 y N están en
	 * la misma componente conexa.
	 */
	ll res = cost(comp[0], comp[n - 1]);
	for (int c = 1; c < cur; c++) {
		// Minimizar el costo de construir dos caminos
		res = min(res, cost(c, comp[0]) + cost(c, comp[n - 1]));
	}
	cout << res << endl;
}
 
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) { solve(); }
}