华为笔试5.20有向图环路—Java

有向图寻找环路（图+dfs）
如有错误，欢迎指出
edges记录邻接矩阵
使用used数组记录当前节点是否被使用过
使用instack数组记录目前节点是否在搜索路径中
stack记录搜索路径
题目描述
给定一个有向图，假定最多10个节点，节点编号依次为A~J，如果A节点到B节点之间有通路则描述为A->B，多条边的描述之间以分号隔开，给定一个有向图，求该有向图中的所有环路，环路以节点编号的最小的节点开始输出，假定一个有向图最多一个环路，如果没有环路则输出空字符串“-”。输入为连接链表。
输入描述:
输入为连接链表字符串，如 ：A->B;B->D;C->B;C->E;D->C
输出描述:
环路节点组成的字符串，如：输出字符串BDC，标识B->D->C->B组成环路
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
A->B;B->D;C->B;C->E;D->C
输出
BDC

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Two {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        // 检查输入合法性
        boolean matches = str.matches("[A-J]\\-\\>[A-J](\\;[A-J]\\-\\>[A-J]){0,9}");
        if (matches) {
            String[] paths = str.split(";");
            // 创建邻接矩阵
            int[][] edges = new int[paths.length][paths.length];
            for (String path : paths) {
                String[] bet = path.split("->");
                int u = bet[0].charAt(0) - 'A';
                int v = bet[1].charAt(0) - 'A';
                edges[u][v] = 1;
            }
            // 定义数组boolean[]，记录结点是否被访问
            boolean[] used = new boolean[edges.length];
            List<Integer> cycle = new ArrayList<Integer>();
            helper(edges, cycle);
            if(cycle.size()==0) {
                System.out.println("-");
                return;
            }
            for (Integer integer : cycle) {
                System.out.print((char)('A'+integer));
            }
        } else {
            System.out.println("-");
            return;
        }
        in.close();
    }

    private static void helper(int[][] edges, List<Integer> cycle) {
        // TODO Auto-generated method stub
        boolean[] used = new boolean[edges.length];
        boolean[] instack = new boolean[edges.length];
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < used.length; i++) {
            if (!used[i]) {
                dfs(i, used, instack, stack, cycle, edges);
            }
        }
    }

    private static void dfs(int i, boolean[] used, boolean[] instack, Stack<Integer> stack, List<Integer> cycle,
            int[][] edges) {
        // TODO Auto-generated method stub
        used[i] = true;
        if (instack[i]) {
            int count = stack.indexOf(i);
            Stack<Integer> tem = new Stack<Integer>();
            tem.addAll(stack);
            while (tem.size() > count) {
                cycle.add(tem.pop());
            }
            Collections.reverse(cycle);
            return;
        }
        instack[i] = true;
        stack.push(i);
        for (int j = 0; j < edges[i].length; j++) {
            if(edges[i][j]!=1)
                continue;
            dfs(j, used, instack, stack, cycle, edges);
        }
        // 回溯
        stack.pop();
        instack[i] = false;
    }

}