Longest Cycle In A Graph - Leetcode Solution

Problem Statement:

Given an undirected graph, find the length of the longest cycle in the graph.

Example:

Input: graph = [[1,2], [2,3], [3,4], [4,5], [5,6], [6,1]] Output: 6

Explanation: The given graph has a cycle of length 6 which is [1,2,3,4,5,6].

Solution:

To solve this problem, we can use the Depth First Search (DFS) algorithm to explore the graph and detect cycles in it.

Algorithm:

1. Initialize a variable max_cycle_length to 0.
2. For each node in the graph, perform a DFS starting from that node and calculate the maximum length of the cycle found.
3. If the length of the cycle found is greater than max_cycle_length, update max_cycle_length with the new value.
4. Return the value of max_cycle_length.

In the DFS algorithm, we need to keep track of the visited nodes and the parent node of each node to detect cycles.

Algorithm for DFS:

1. Initialize a visited array to keep track of the visited nodes and a parent array to keep track of the parent node of each node.
2. For each unvisited node, perform a DFS starting from that node.
3. In the DFS function, mark the current node as visited and iterate over all its neighbors.
4. If a neighbor is not visited, set its parent to the current node and recursively call the DFS function on it.
5. If a neighbor is visited and its parent is not the current node, it means that a cycle is found. In this case, calculate the length of the cycle by counting the number of nodes from the current node to the neighbor node and return it.
6. If a neighbor is visited and its parent is the current node, it means that we are backtracking and there is no cycle. In this case, return 0.

Python Code:

class Solution: def maxCycleLength(self, graph: List[List[int]]) -> int: n = len(graph) max_cycle_length = 0

    def dfs(node, parent, visited):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                parent[neighbor] = node
                cycle_length = dfs(neighbor, parent, visited)
                if cycle_length > 0:
                    return cycle_length + 1
            elif neighbor != parent[node]:
                return 2
        
        return 0
    
    for i in range(n):
        visited = [False] * n
        parent = [-1] * n
        cycle_length = dfs(i, parent, visited)
        max_cycle_length = max(max_cycle_length, cycle_length)
    
    return max_cycle_length

Time Complexity:

The time complexity of the DFS algorithm is O(E+V) where E is the number of edges and V is the number of vertices in the graph. We perform a DFS for each node, so the overall time complexity of the solution is O(V*(E+V)).

Space Complexity:

The space complexity of the DFS function is O(V) for the visited and parent arrays. We call the DFS function V times, so the overall space complexity of the solution is O(V^2).

1