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);
        System.out.println(res);
        
        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) {
        if(currVisited.contains(cur)) return;
        currVisited.add(cur);
        visited.add(cur);
        if(nodes.containsKey(cur)) {
            for(Integer edge : nodes.get(cur)) {
                if(edge != start && res.contains(edge)) 
                    res.remove(edge);
                search(res, nodes, edge, 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 i = 0; i < n; i++) {
            g.put(i, new HashSet<>());
        }
        for(int[] edge : edges) {
            g.get(edge[0]).add(edge[1]);
        }
        Set<Integer> visited = new HashSet<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        for(int i = 0; i < n; i++) {
            if(!visited.contains(i)) {
                res.add(i);
                visited.add(i);
                search(res, g, i, i, visited, new HashSet<Integer>());
            }
        }
        return new ArrayList<>(res);
    }
}


run \| edit \| history \| help	0

Please log in to post a comment.

Advertise here.