Undirected graph: cycle recovery

Question

I have next task: Given an undirected graph. You need to determine whether it contains a cycle, and, if so, print it.

Input data

The first line contains one number n — the number of vertices in the graph (1 ≤ n ≤ 500). Next, in n lines the graph itself is specified by the adjacency matrix.

Output data

If there is no cycle in the source graph, then print “NO”. Otherwise, in the first line print “YES”, in the second line print the number k - the number of vertices in the cycle, and in the third line print k different numbers - the numbers of vertices that belong to the cycle in traversal order (the traversal can start from any vertex of the cycle). If there are several loops, then print any.

Examples: Inp

3
0 1 1
1 0 1
1 1 0

Out

YES
3
3 2 1

Inp

4
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0

Out

NO

I have next code:

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

class Solution {
    fun findCycle(n: Int, graph: Array<IntArray>): List<Int>? {
        val visited = BooleanArray(n)
        val parent = IntArray(n) { -1 }

        fun dfs(v: Int): List<Int>? {
            visited[v] = true
            for (u in 0 until n) {
                if (graph[v][u] == 1) {
                    if (!visited[u]) {
                        parent[u] = v
                        val cycle = dfs(u)
                        if (cycle != null) return cycle
                    } else if (parent[v] != u) {
                        val cycle = mutableListOf<Int>()
                        var cur = v
                        while (cur != -1) {
                            cycle.add(cur + 1)
                            cur = parent[cur]
                        }
                        return cycle.reversed()
                    }
                }
            }
            return null
        }

        for (v in 0 until n) {
            if (!visited[v]) {
                val cycle = dfs(v)
                if (cycle != null) return cycle
            }
        }

        return null
    }
}

fun main() {
    val solution = Solution()
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine()!!.toInt()
    val graph = Array(n) { IntArray(n) }
    for (i in 0 until n) {
        graph[i] = reader.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    }

    val cycle = solution.findCycle(n, graph)
    if (cycle != null) {
        writer.write("YES\n")
        writer.write("${cycle.size}\n")
        writer.write("${cycle.joinToString(" ")}\n")
    } else {
        writer.write("NO\n")
    }

    reader.close()
    writer.close()
}

I'm using DFS with visited flag array for cycle detection. For cycle recovery parents array is used. But my solution is not fully accepted to the system (not all test cases are passed). Could you please help me to find an issue here?

Answer 1

I see two logic issues with your code:

1. Re-visiting a node does not mean that you have a cycle. Consider the simple undirected graph A - B - C. If you start once at A and once at C, you will visit B twice, and from different parents.
2. Following the "parent" chain does not stop early enough; you may go beyond the cycle. Consider A - B - C - D - B. The cycle here is B - C - D - B, but if your DFS starts at A, you will be returning A - B - C - D - B since B is the "root" of your DFS.

I would fix them as follows:

1. A simple "visited" boolean array is not enough. You want to distinguish
   1. not seen - encountering a previously unseen node marks it as "in progress";
   2. in progress (still processing descendants) - if you encounter such a node, you have a cycle;
   3. finished - encountering a finished node is not a cycle, hence why a boolean array is not enough
2. When you encountered a cycle, you encountered some node u that was already in progress. Simply loop until you've reached that node, rather than looping until you've found a DFS "root".

Note also that you don't need to reverse the list (the graph is undirected, reverse order is just as valid a traversal order) and that you don't need the "parent" mapping; after all the cycle is still in the local variables stored on your call stack. Here's a somewhat hacky way to retrieve the cycle from there:

enum class NodeState {Unseen, InProgress, Finished}
enum class TraversalState {CollectingCycle, CollectedCycle, Done}
fun findCycle(n: Int, graph: Array<Array<Int>>): List<Int>? {
    val state = Array<NodeState> (n) { NodeState.Unseen }
    val cycle = mutableListOf<Int>()
    var cycleNode = -1
    fun findCycle(v: Int, parent: Int): TraversalState {
        // Encountered an in-progress node => cycle!
        if (state[v] == NodeState.InProgress) {
            cycleNode = v
            return TraversalState.CollectingCycle
        }
        state[v] = NodeState.InProgress
        neighbors@ for (u in 0 until n) {
            if (graph[v][u] == 0 || u == parent) continue
            if (state[u] == NodeState.Finished) continue
            when (findCycle(u, v)) {
                TraversalState.Done -> {
                    continue@neighbors
                }
                TraversalState.CollectedCycle -> {
                    return TraversalState.CollectedCycle
                }
                TraversalState.CollectingCycle -> {
                    cycle.add(v)
                    if (cycleNode == v)
                        return TraversalState.CollectedCycle
                    return TraversalState.CollectingCycle
                }
            }
        }
        state[v] = NodeState.Finished
        return TraversalState.Done
    }
    for (v in 0 until n) {
        if (state[v] != NodeState.Unseen) continue
        // No need to reverse, any traversal order is valid
        if (findCycle(v, -1) == TraversalState.CollectedCycle) return cycle
    }
    return null
}

which for your two examples

println(findCycle(3, arrayOf(arrayOf(0, 1, 1), arrayOf(1, 0, 1), arrayOf(1, 1, 0))))
println(findCycle(4, arrayOf(arrayOf(0, 0, 1, 0), arrayOf(0, 0, 0, 1), arrayOf(1, 0, 0, 0), arrayOf(0, 1, 0, 0))))

works correctly, printing [2, 1, 0] and null respectively.

Note: You'll still need to add one to the vertices, e.g. using a simple map { it + 1 }. I considered adding this I/O to findCycle dirty.