# Shortest Cycle in a Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-cycle-in-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/shortest-cycle-in-a-graph
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## Problem
There is a **bi-directional** graph with `n` vertices, where each vertex is labeled from `0` to `n - 1`. The edges in the graph are represented by a given 2D integer array `edges`, where `edges[i] = [ui, vi]` denotes an edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

Return _the length of the **shortest** cycle in the graph_. If no cycle exists, return `-1`.

A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.

**Example 1:**

![](https://assets.glich.co/dsa/shortest-cycle-in-a-graph/image0.png) 

**Input:** n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
**Output:** 3
**Explanation:** The cycle with the smallest length is : 0 -> 1 -> 2 -> 0 

**Example 2:**

![](https://assets.glich.co/dsa/shortest-cycle-in-a-graph/image1.png) 

**Input:** n = 4, edges = [[0,1],[0,2]]
**Output:** -1
**Explanation:** There are no cycles in this graph.

**Constraints:**

* `2 <= n <= 1000`
* `1 <= edges.length <= 1000`
* `edges[i].length == 2`
* `0 <= ui, vi < n`
* `ui != vi`
* There are no repeated edges.

# Approaches
## BFS from Each Node
This approach iterates through every node in the graph and uses it as a starting point for a Breadth-First Search (BFS). The goal of each BFS is to find the shortest cycle that includes the starting node. By performing this search from every node, we ensure that we find the overall shortest cycle in the entire graph.
**Time:** O(V * (V + E)), where V is the number of vertices (n) and E is the number of edges. We run a BFS from each of the V vertices, and each BFS takes O(V + E) time. · **Space:** O(V + E), where V is the number of vertices and E is the number of edges. This is for storing the adjacency list. The BFS itself requires O(V) space for the queue, distance, and parent arrays.
**Pros:** Conceptually straightforward and relatively easy to implement.; Guaranteed to find the shortest cycle by exhaustively checking from every possible node.
**Cons:** Less efficient than the edge-based approach, especially when the number of edges is much smaller than the number of vertices.; The time complexity is proportional to `V * (V + E)`, which can be slow if `V` is large.
### Explanation
The algorithm works by systematically exploring the graph from each vertex. For each vertex `i` from `0` to `n-1`, we perform a BFS. During the BFS starting from `i`, we keep track of the distance of each node from `i` and its parent in the BFS tree. A cycle is detected when we are at a node `u` and we encounter an adjacent node `v` that has already been visited and is not the immediate parent of `u`. The length of such a cycle is the sum of their distances from the start node `i`, plus one for the edge `(u, v)`. We keep track of the minimum cycle length found across all starting nodes.

```java
import java.util.*;

class Solution {
    public int findShortestCycle(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int shortestCycle = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int[] dist = new int[n];
            Arrays.fill(dist, -1);
            int[] parent = new int[n];
            Arrays.fill(parent, -1);

            Queue<Integer> q = new LinkedList<>();
            q.add(i);
            dist[i] = 0;

            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.add(v);
                    } else if (v != parent[u]) {
                        shortestCycle = Math.min(shortestCycle, dist[u] + dist[v] + 1);
                    }
                }
            }
        }

        return shortestCycle == Integer.MAX_VALUE ? -1 : shortestCycle;
    }
}
```
### Algorithm
*   Build an adjacency list representation of the graph.
*   Initialize a variable `min_cycle` to a value representing infinity.
*   Iterate through each vertex `i` from `0` to `n-1`, treating it as the starting node for a Breadth-First Search (BFS).
*   For each `start_node` `i`:
    *   Initialize a `distance` array (to store distances from `i`) and a `parent` array (to track the path) for all nodes, marking them as unvisited (e.g., with -1).
    *   Create a queue and add the `start_node` `i`. Set its distance to 0.
    *   While the queue is not empty, dequeue a node `u`.
    *   For each neighbor `v` of `u`:
        *   If `v` has not been visited (`distance[v] == -1`), update its distance and parent, and enqueue it.
        *   If `v` has been visited and is not the parent of `u` in the current BFS tree (`v != parent[u]`), a cycle has been found.
        *   The length of this cycle is `distance[u] + distance[v] + 1`.
        *   Update `min_cycle` with the minimum length found so far.
*   After checking all nodes as starting points, if `min_cycle` is still infinity, no cycles exist. Return -1. Otherwise, return `min_cycle`.

## BFS on Edge Removal
A more optimized approach involves iterating through each edge of the graph instead of each vertex. For each edge `(u, v)`, we can think of it as the final edge that closes a cycle. The rest of the cycle is simply a path between `u` and `v`. To find the shortest cycle involving edge `(u, v)`, we need to find the shortest path between `u` and `v` that doesn't use the edge `(u, v)` itself. We can find this path using a BFS. By repeating this for every edge, we can find the overall shortest cycle.
**Time:** O(E * (V + E)), where V is the number of vertices (n) and E is the number of edges. We iterate through each of the E edges, and for each, we perform a BFS that takes O(V + E) time. · **Space:** O(V + E), where V is the number of vertices and E is the number of edges. This space is used for the adjacency list and the data structures within the BFS (queue, distance array).
**Pros:** More efficient than the node-based BFS approach for sparse graphs (where E < V), which is the case for the given constraints.; Directly targets the structure of a cycle (an edge and a path), leading to a more focused search.
**Cons:** The implementation requires careful handling of the 'removed' edge within the BFS traversal.; While generally efficient for the given constraints, its polynomial time complexity might not be suitable for extremely large graphs.
### Explanation
The core idea is that any cycle is composed of an edge `(u, v)` and an alternative path between `u` and `v`. This approach systematically finds the shortest such structure. We iterate through all edges. For each edge `(u, v)`, we perform a BFS starting from `u` to find the shortest path to `v`. A key detail is to modify the BFS to ignore the direct edge from `u` to `v`. If the BFS finds `v` at a distance `d`, we have discovered a cycle of length `d + 1`. We take the minimum over all such cycles found.

```java
import java.util.*;

class Solution {
    public int findShortestCycle(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int shortestCycle = Integer.MAX_VALUE;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            // Find shortest path from u to v without using edge (u,v)
            int pathLength = bfs(u, v, n, adj);
            if (pathLength != -1) {
                shortestCycle = Math.min(shortestCycle, pathLength + 1);
            }
        }

        return shortestCycle == Integer.MAX_VALUE ? -1 : shortestCycle;
    }

    private int bfs(int startNode, int endNode, int n, List<Integer>[] adj) {
        Queue<int[]> q = new LinkedList<>(); // {node, distance}
        q.add(new int[]{startNode, 0});
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[startNode] = 0;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int u = current[0];
            int d = current[1];

            if (u == endNode) {
                return d;
            }

            for (int neighbor : adj[u]) {
                // The crucial part: ignore the direct edge between startNode and endNode
                if (u == startNode && neighbor == endNode) {
                    continue;
                }
                if (dist[neighbor] == -1) {
                    dist[neighbor] = d + 1;
                    q.add(new int[]{neighbor, d + 1});
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Build an adjacency list representation of the graph.
*   Initialize a variable `min_cycle` to a value representing infinity.
*   Iterate through each edge `(u, v)` from the input `edges` array.
*   For each edge, temporarily consider it removed from the graph.
*   Find the shortest path distance between `u` and `v` in the graph without this edge. This can be done using a Breadth-First Search (BFS) starting from `u`.
*   In the BFS starting from `u` to find `v`, ensure that the direct edge `(u, v)` is not used. This is typically done by skipping `v` when exploring the neighbors of `u`.
*   If a path from `u` to `v` is found with length `d`, it forms a cycle of length `d + 1` with the original edge `(u, v)`.
*   Update `min_cycle = min(min_cycle, d + 1)`.
*   After iterating through all edges, if `min_cycle` is still infinity, no cycles exist. Return -1. Otherwise, return `min_cycle`.

# Solutions
### Java

```java
class Solution { private List < Integer >[] g ; private final int inf = 1 << 30 ; public int findShortestCycle ( int n , int [][] edges ) { g = new List [ n ]; Arrays . setAll ( g , k -> new ArrayList <>()); for ( var e : edges ) { int u = e [ 0 ], v = e [ 1 ]; g [ u ]. add ( v ); g [ v ]. add ( u ); } int ans = inf ; for ( var e : edges ) { int u = e [ 0 ], v = e [ 1 ]; ans = Math . min ( ans , bfs ( u , v )); } return ans < inf ? ans : - 1 ; } private int bfs ( int u , int v ) { int [] dist = new int [ g . length ]; Arrays . fill ( dist , inf ); dist [ u ] = 0 ; Deque < Integer > q = new ArrayDeque <>(); q . offer ( u ); while (! q . isEmpty ()) { int i = q . poll (); for ( int j : g [ i ]) { if (( i == u && j == v ) || ( i == v && j == u ) || dist [ j ] != inf ) { continue ; } dist [ j ] = dist [ i ] + 1 ; q . offer ( j ); } } return dist [ v ] + 1 ; } }
```

### CPP

```cpp
class Solution {
public:
  int findShortestCycle(int n, vector<vector<int>> &edges) {
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      g[u].push_back(v);
      g[v].push_back(u);
    }
    const int inf = 1 << 30;
    auto bfs = [&](int u, int v) -> int {
      int dist[n];
      fill(dist, dist + n, inf);
      dist[u] = 0;
      queue<int> q{{u}};
      while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j : g[i]) {
          if ((i == u && j == v) || (i == v && j == u) || dist[j] != inf) {
            continue;
          }
          dist[j] = dist[i] + 1;
          q.push(j);
        }
      }
      return dist[v] + 1;
    };
    int ans = inf;
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      ans = min(ans, bfs(u, v));
    }
    return ans < inf ? ans : -1;
  }
};

```

### Python

```python
class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int: def bfs(u: int, v: int) -> int: dist = [inf] * n dist[u] = 0 q = deque([u]) while q: i = q . popleft() for j in g[i]: if (i, j) != (u, v) and (j, i) != (u, v) and dist[j] == inf: dist[j] = dist[i] + 1 q . append(j) return dist[v] + 1 g = defaultdict(set) for u, v in edges: g[u]. add(v) g[v]. add(u) ans = min(bfs(u, v) for u, v in edges) return ans if ans < inf else - 1

```