666768697071727374757677787980818283848586

package main

import "fmt"

// dfs performs DFS traversal to detect cycle in directed graph
func dfs(node int, adj [][]int, visited, pathVisited []bool) bool {

	// Mark the node as visited
	visited[node] = true

	// Mark the node as path visited
	pathVisited[node] = true

	// Traverse all the neighbors
	for _, it := range adj[node] {

		/* If the neighbor is already visited
		in the path, a cycle is detected */
		if pathVisited[it] {
			return true
		}

		/* Else if the node is unvisited,
		perform DFS recursively from this node */
		if !visited[it] {
			// If cycle is detected, return true
			if dfs(it, adj, visited, pathVisited) {
				return true
			}
		}
	}

	// Remove the node from path
	pathVisited[node] = false

	// Return false if no cycle is detected
	return false
}

// Function to detect cycle in a directed graph
func isCyclic(V int, adj [][]int) bool {

	// Visited array
	visited := make([]bool, V)

	/* Array to mark nodes that are
	visited in a particular path */
	pathVisited := make([]bool, V)

	// Traverse the graph
	for i := 0; i < V; i++ {
		if !visited[i] {
			// If a cycle is found, return true
			if dfs(i, adj, visited, pathVisited) {
				return true
			}
		}
	}

	/* Return false if no cycle is
	detected in any component */
	return false
}

func main() {
	V := 6
	adj := [][]int{
		{1},
		{2, 5},
		{3},
		{4},
		{1},
		{},
	}

	// Function call to determine if cycle exists in given directed graph
	ans := isCyclic(V, adj)

	// Output
	if ans {
		fmt.Println("The given directed graph contains a cycle.")
	} else {
		fmt.Println("The given directed graph does not contain a cycle.")
	}
}

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple DFS traversal takes O(V+E) time.

Space Complexity: O(V)
The visited array and Path Visited array take O(V) space each and the recursion stack space during DFS traversal will be O(V).

1d:T68cb,

Intuition:

To solve this problem using BFS traversal, the previously known algorithm Topological Sort can be used.

Recall that Topological Ordering for a graph having V nodes can be determined if and only the graph is a Directed Acyclic Graph, i.e., there must be no cycle present in the directed graph. In other words, the topological ordering of a DAG consisting of V nodes will always contain V nodes.

But this is not true in the case of a Directed Cyclic Graph. In such a graph where the number of nodes is V, the topological ordering will not contain all nodes (because of the presence of a cycle).

Thus, if the topological sort of the directed graph contains all nodes of the graph, then the graph is acyclic otherwise it is cyclic.

Approach:

A helper function is defined to get the topological sort for the given graph using Kahn's algorithm (BFS based).
The topological ordering for the given directed graph is found using the helper function.
If the ordering contains all nodes, the directed graph is cyclic. Otherwise it is acyclic.

Dry Run: