Shortest Cycle in a Graph

class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        int best = INT_MAX;
        for (int s = 0; s < n; ++s) {
            vector<int> dist(n, -1), parent(n, -1);
            dist[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.push(v);
                    } else if (parent[u] != v) {
                        best = min(best, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        return best == INT_MAX ? -1 : best;
    }
};

import "math"

func findShortestCycle(n int, edges [][]int) int {
    adj := make([][]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        adj[e[1]] = append(adj[e[1]], e[0])
    }
    best := math.MaxInt32
    for s := 0; s < n; s++ {
        dist := make([]int, n)
        parent := make([]int, n)
        for i := range dist {
            dist[i] = -1
            parent[i] = -1
        }
        dist[s] = 0
        q := []int{s}
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            for _, v := range adj[u] {
                if dist[v] == -1 {
                    dist[v] = dist[u] + 1
                    parent[v] = u
                    q = append(q, v)
                } else if parent[u] != v {
                    if c := dist[u] + dist[v] + 1; c < best {
                        best = c
                    }
                }
            }
        }
    }
    if best == math.MaxInt32 {
        return -1
    }
    return best
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        best = float('inf')
        for s in range(n):
            dist = [-1] * n
            parent = [-1] * n
            dist[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if dist[v] == -1:
                        dist[v] = dist[u] + 1
                        parent[v] = u
                        q.append(v)
                    elif parent[u] != v:
                        c = dist[u] + dist[v] + 1
                        if c < best:
                            best = c
        return -1 if best == float('inf') else best

function findShortestCycle(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        adj[a].push(b);
        adj[b].push(a);
    }
    let best = Infinity;
    for (let s = 0; s < n; s++) {
        const dist = new Array(n).fill(-1);
        const parent = new Array(n).fill(-1);
        dist[s] = 0;
        const q = [s];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of adj[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.push(v);
                } else if (parent[u] !== v) {
                    const c = dist[u] + dist[v] + 1;
                    if (c < best) best = c;
                }
            }
        }
    }
    return best === Infinity ? -1 : best;
}

class Solution {
    public int findShortestCycle(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int best = Integer.MAX_VALUE;
        for (int s = 0; s < n; s++) {
            int[] dist = new int[n];
            int[] parent = new int[n];
            Arrays.fill(dist, -1);
            Arrays.fill(parent, -1);
            dist[s] = 0;
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.offer(v);
                    } else if (parent[u] != v) {
                        best = Math.min(best, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

function findShortestCycle(n: number, edges: number[][]): number {
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        adj[a].push(b);
        adj[b].push(a);
    }
    let best = Infinity;
    for (let s = 0; s < n; s++) {
        const dist: number[] = new Array(n).fill(-1);
        const parent: number[] = new Array(n).fill(-1);
        dist[s] = 0;
        const q: number[] = [s];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of adj[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.push(v);
                } else if (parent[u] !== v) {
                    const c = dist[u] + dist[v] + 1;
                    if (c < best) best = c;
                }
            }
        }
    }
    return best === Infinity ? -1 : best;
}