华为机试0406 第二题（DFS）

DFS版本 思路：

DFS 判断是否有环，只要一条路径有环就不行，直接返回输出-1； 在 DFS 过程中使用 TreeSet 记录所有依赖点即可，如果不存在环，就是所有的依赖点了。

package huawei.oj_0406;

import java.util.*;

public class Solution2 {
          
   
    private static boolean haveLoop = false;
    private static Set<Integer> dependments;
    private static int m;
    public static void main(String[] args) {
          
   
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        m = Integer.parseInt(sc.nextLine());
        List<Integer>[] parents = new List[n];
        for(int i = 0; i < n; i++){
          
   
            parents[i] = new ArrayList<>();
            String[] strs = sc.nextLine().split(",");
            int k = Integer.parseInt(strs[0]);
            for(int j = 1; j <= k; j++)
                parents[i].add(Integer.parseInt(strs[j]));
        }

        dependments = new TreeSet<>();
        dfs(parents, m, new boolean[n]);
        if(haveLoop)
            System.out.println(-1);
        else{
          
   
            Integer[] res = dependments.toArray(new Integer[0]);
            System.out.print(res[0]);
            for(int i = 1; i < res.length; i++)
                System.out.print("," + res[i]);
        }
    }

    private static void dfs(List<Integer>[] parents, int i, boolean[] visited){
          
   
        if(visited[i] == true){
          
   
            haveLoop = true;
            return;
        }
        if(!haveLoop){
          
   
            if(m != i)
                dependments.add(i);
            visited[i] = true;
            for(int j : parents[i])
                dfs(parents, j, visited);
            visited[i] = false;
        }
    }
}