Graph Girth

Solución en video

Por David Zhou

Código de la solución en video

C++JavaPython


#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int n;
 
int bfs(int start, vector<vector<int>> &adj) {
	vector<int> dist(n, -1);
	dist[start] = 0;
	vector<int> parent(n, -1);
 
	queue<int> q;
	q.push(start);
	int min_cycle = INT_MAX;
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int next : adj[curr]) {
			if (dist[next] == -1) {
				parent[next] = curr;
				dist[next] = dist[curr] + 1;
				q.push(next);
			} else if (parent[curr] != next) {
				// si la siguiente celda no es el padre asignado, hay un ciclo
				min_cycle = min(min_cycle, dist[curr] + dist[next] + 1);
			}
		}
	}
 
	return min_cycle;
}
 
int main() {
	int m;
	cin >> n >> m;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	int res = INT_MAX;
	// suponemos que el nodo actual es parte del ciclo más corto
	for (int i = 0; i < n; i++) { res = min(res, bfs(i, adj)); }
 
	cout << (res == INT_MAX ? -1 : res) << endl;
}


import java.io.*;
import java.util.*;
 
public class GraphGirth {
	private static int n;
	private static int[] dist;
	private static int[] parent;
	private static ArrayDeque<Integer> q = new ArrayDeque<>();
 
	private static int bfs(int start, List<List<Integer>> adj, int currMin) {
		Arrays.fill(dist, -1);
		Arrays.fill(parent, -1);
		q.clear();
 
		dist[start] = 0;
		q.add(start);
		int minCycle = currMin;
 
		while (!q.isEmpty()) {
			int curr = q.poll();
			for (int next : adj.get(curr)) {
				if (dist[next] == -1) {
					parent[next] = curr;
					dist[next] = dist[curr] + 1;
					q.add(next);
				} else if (parent[curr] != next) {
					// si la siguiente celda no es el padre asignado, hay un ciclo
					int cycleLen = dist[curr] + dist[next] + 1;
					if (cycleLen < minCycle) { minCycle = cycleLen; }
				}
			}
		}
 
		return minCycle;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		List<List<Integer>> adj = new ArrayList<>();
		for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); }
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		dist = new int[n];
		parent = new int[n];
 
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			// suponemos que el nodo actual es parte del ciclo más corto
			if (adj.get(i).size() < 2) continue;  // no es posible un ciclo
			res = Math.min(res, bfs(i, adj, res));
		}
 
		System.out.println(res == Integer.MAX_VALUE ? -1 : res);
	}
}


import sys
from collections import deque
from typing import List
 
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
 
 
def bfs(start: int, adj: List[List[int]]) -> int:
	dist = [-1] * n
	dist[start] = 0
	parent = [-1] * n
 
	q = deque()
	q.append(start)
	min_cycle = float("inf")
	while q:
		curr = q.popleft()
		for next in adj[curr]:
			if dist[next] == -1:
				parent[next] = curr
				dist[next] = dist[curr] + 1
				q.append(next)
			elif parent[curr] != next:
				# si la siguiente celda no es el padre asignado, hay un ciclo
				min_cycle = min(min_cycle, dist[curr] + dist[next] + 1)
 
	return min_cycle
 
 
res = float("inf")
for i in range(n):  # suponemos que el nodo actual es parte del ciclo más corto
	res = min(res, bfs(i, adj))
 
print(-1 if res == float("inf") else res)

Explicación

Consideremos un problema más simple: dado un grafo, hallar el ciclo más corto que pasa por el nodo 1.

¿Cómo se ve un ciclo que pasa por el nodo 1? En cualquier ciclo que pasa por el nodo 1, existen dos nodos $u$ y $v$ en ese ciclo tales que hay un camino de 1 a $u$ y de 1 a $v$ , y hay una arista entre $u$ y $v$ . La longitud de este ciclo es $dist(1, u) + dist(1, v) + 1$ .

Uno podría intentar usar BFS para hallar $dist(1, i)$ para cada $i$ en tiempo $\mathcal{O}(N + M)$ y luego revisar, para cada arista $(u, v)$ , si $dist(1, u) + dist(1, v) + 1$ es mínimo.

Por supuesto, esto significa que podríamos contar un “ciclo” como $1 \rightarrow x \rightarrow u \rightarrow v \rightarrow x \rightarrow 1$ . Sin embargo, esto no importa para nuestro problema original, porque el ciclo más corto siempre será más corto que un “ciclo” de ese tipo.

Hay un problema con este enfoque: si la arista $(u, v)$ está en el camino del nodo 1 al nodo $v$ , entonces $1 \rightarrow u \rightarrow v \rightarrow 1$ ¡no es un ciclo! Y esta vez sí importa en nuestro problema original.

Afortunadamente, hay una corrección relativamente simple.

En lugar de primero hallar todos los $dist(1, i)$ y después revisar el mínimo, hacemos ambas cosas al mismo tiempo durante el BFS.

Ahora, para evitar “volver sobre nuestros pasos”, solo consideramos $dist(1, u) + dist(1, v) + 1$ como un mínimo si estamos actualmente en el nodo $u$ y $dist(1, u) \leq dist(1, v)$ .

Este algoritmo corre en tiempo $\mathcal{O}(N + M)$ . Como $N$ y $M$ son tan chicos, podemos aplicar este algoritmo para todos los nodos en lugar de solo el nodo 1.

La complejidad final de esta solución es entonces $\mathcal{O}(N(N + M))$ .

Implementación

C++


#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
const int maxn = 2510;
const int inf = 1000000007;
 
int n, m;
vector<int> adj[maxn];
 
int cycle_len(int start) {
	int ans = inf;
 
	vector<int> dist(n, -1);
	queue<int> bfs;
 
	dist[start] = 0;
	bfs.push(start);
 
	while (!bfs.empty()) {
		int node = bfs.front();
		bfs.pop();
 
		for (int adj_node : adj[node]) {
			if (dist[adj_node] == -1) {
				dist[adj_node] = dist[node] + 1;
				bfs.push(adj_node);
			} else if (dist[adj_node] >= dist[node]) {
				ans = min(ans, 1 + dist[adj_node] + dist[node]);
			}
		}
	}
 
	return ans;
}
 
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	int res = inf;
	for (int i = 0; i < n; i++) { res = min(res, cycle_len(i)); }
 
	if (res == inf) {
		cout << -1 << endl;
		return 0;
	}
 
	cout << res << endl;
}

Una aproximación +1 más rápida

¿Podemos mejorar la complejidad temporal de la solución de arriba cuando $M\gg N$ ? El código de abajo reduce la complejidad temporal a $\mathcal{O}(N^2)$ cortando apenas el BFS visita el mismo vértice dos veces. Sin embargo, es posible que devuelva la longitud del ciclo más corto más uno en lugar de la longitud exacta del ciclo más corto, así que no pasa todos los tests de CSES.


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m;
	cin >> n >> m;
 
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	int answer = INT_MAX;
 
	for (int i = 0; i < n; ++i) {  // bfs desde i
		vector<int> dist(n, -1);
		queue<int> q;
		q.push(i);
		dist[i] = 0;
 
		while (!q.empty()) {
			int x = q.front();
			q.pop();
 
			for (int t : adj[x]) {
				if (dist[t] == -1) {
					dist[t] = dist[x] + 1;
					q.push(t);
				} else if (dist[t] >= dist[x]) {
					answer = min(answer, dist[t] + dist[x] + 1);
					goto DONE;
				}
			}
		}
	DONE:;
	}
 
	cout << (answer == INT_MAX ? -1 : answer) << '\n';
}