Minimum Vertices to Traverse Directed Graph, Java

Minimum Vertices to Traverse Directed Graph

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int[][] edges = {{2,9},{3,3},{3,5},{3,7},{4,8},{5,8},{6,6},{7,4},{8,7},{9,3},{9,6}};
        List<Integer> res = getMin(edges, 10);
        for (int num : res) {
            System.out.println(num);
        }
        
        edges = new int[][]{{0, 0}, {1, 2}, {2, 0}, {2, 3}, {3, 1}};
        res = getMin(edges, 4);
        System.out.println(res);
        assert 1 == res.size();
        
        edges =  new int[][]{{0, 1}, {1, 0}, {2, 1}, {2, 3}, {3, 2}};
        res = getMin(edges, 4);
        System.out.println(res);
        assert 1 == res.size();
        
        edges =  new int[][]{{0, 1}, {1, 0}, {2, 1}, {3, 1}, {3, 2}};
        res = getMin(edges, 4);
        System.out.println(res);
        assert 1 == res.size();

edges =  new int[][]{{2, 9}, {3, 3}, {3, 5}, {3, 7}, {4, 8}, {5, 8}, {6, 6}, {7, 4}, {8, 7}, {9, 3}, {9, 6}};
        res = getMin(edges, 10);
        System.out.println(res);
        assert 3 == res.size();

}
    
    private static void search(Set<Integer> res, Map<Integer, Set<Integer>> nodes, int cur, int start,
                            Set<Integer> visited, Set<Integer> currVisited) {
            currVisited.add(cur);
            visited.add(cur);
            for (int next : nodes.get(cur)) {
                if (res.contains(next) && next != start) {
                    res.remove(next);
                }
                if (!currVisited.contains(next)) {
                    search(res, nodes, next, start, visited, currVisited);
                }
            }
        }
    
    private static List<Integer> getMin(int[][] edges, int n) {
        if(edges == null || edges.length == 0) return null;
        Map<Integer, Set<Integer>> g = new TreeMap<>();
        for(int[] edge : edges) {
            if(!g.containsKey(edge[0])) g.put(edge[0], new HashSet<Integer>());
            if(!g.containsKey(edge[1])) g.put(edge[1], new HashSet<Integer>());
            g.get(edge[0]).add(edge[1]);
        }
        
        Set<Integer> visited = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        int cnt = 0;
        for(int i : g.keySet()) {
            if(cnt == n) break;
            if (!visited.contains(i)) {
                 res.add(i);
                 visited.add(i);
                 search(res, g, i, i, visited, new HashSet<>());
                 cnt++;
            }  
        }
        
        return new ArrayList<>(res);
    }
}


run \| edit \| history \| help	0