graph_detect_cycle.go

package main

func isCyclic(n int, adj [][]int) bool {
	vis := make([]bool, n)
	var dp = make([]bool, n) //true when all path traversed and with no loop i.e. memoization for no cycles starting this index
	for i := 0; i < n; i++ {
		if dp[i] {
			continue
		}

		if dfs_util(i, vis, dp, adj) {
			return false
		}
		vis[i] = false
		dp[i] = true

	}
	return true
}

func dfs_util(num int, vis, dp []bool, adj [][]int) bool {
	if vis[num] == true {
		return true
	}

	vis[num] = true

	for _, n := range adj[num] {
		ans := false
		if !dp[n] {
			ans = dfs_util(n, vis, dp, adj)
		}
		if ans {
			return true
		}
		vis[n] = false

	}
	dp[num] = true
	return false

}