有向和断开连接图中的周期检测

Question

我正在尝试找出图是否包含周期。我已经应用了DFS。问题在于我的代码将任何图表分类为循环图。

这是我的代码：

public class Graph {
    public static int nodeno;
    public static int edgeno;
    public static int graph[][];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        nodeno = in.nextInt();
        edgeno = in.nextInt();
        graph = new int[nodeno][nodeno];
        for (int i = 0; i < edgeno; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            graph[from][to] = 1;
        }
        if (isCyclic())
            System.out.println("Contain cycle");
        else
            System.out.println("No Cycle");
    }
    private static boolean isCyclic() {
        boolean[] visit = new boolean[nodeno];
        boolean[] recStack = new boolean[nodeno];
        for (int i = 0; i < nodeno; i++) {
            if (isCyclicUtil(i, visit, recStack))
                return true;
        }
        return false;
    }
    private static boolean isCyclicUtil(int s, boolean[] visit, boolean[] recStack) {
        if (visit[s] == false) {
            visit[s] = true;
            recStack[s] = true;
            for (int i = 0; i < nodeno; i++) {
                if (graph[s][i] == 1) {
                    if (!visit[i] && isCyclicUtil(i, visit, recStack))
                        return true;
                    else if (recStack[i])
                        return true;
                }
            }
        }
        recStack[s] = false;
        return false;
    }
}

我的样本输入是

4
5
0 1 1 0
0 0 1 1
0 0 0 1
0 0 0 0

这里的输出应为No cycle，但它显示contain cycle。找不到我的错。有没有帮助我？

Answer 1

样本输入与读取器格式不匹配。读者期望边缘列表，而不是邻接矩阵。根据您使用的格式，所提供的图确实是循环的：边缘为0-> 1，1-> 0 ..

可能是您的意思：

4
5
0 1
0 2
1 2
1 3
2 3