Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.6 kB
3
Indexable
Never
private boolean isCyclicUtil(String i, Map<String,Boolean> visited,
                                      Map<String,Boolean> recStack, Map<String,String> adjMap)
    {
        if (recStack.contains(i))
            return true;
 
        if (visited.contains(i))
            return false;
             
        visited.put(i,true)
 
        recStack.put(i,true)

        List<String> children = adjMap.get(i);
         
        for (String c: children)
            if (isCyclicUtil(c, visited, recStack))
                return true;
                 
        recStack[i] = false;
 
        return false;
    }
    
    public static void main(String[] transactions, String[] queries){
        
        Map<String,List<String>> adjMap = new HashMap<>();
        
        for(String[] q : transactions){
            List<String> li = adjMap.getOrDefault(q[0], new ArrayList<>());
            li.add(q[1]);
            adjMap.put(q[0],li);
        }
        List<Map.Entry<String,List<String>> liEntry = new ArrayList(adjMap.entrySet());
        boolean[] result = new boolean[queries.length];
        for(String[] q : queries){
            Map<String,Boolean> visited = new HashMap<>();
            Map<String,Boolean> recStack = new HashMap<>();
            String user1 = q[0];
            String user2 = q[1];
            if (isCyclicUtil(user1, visited, recStack, adjMap) && visited.containsKey(user2))
                result[i] = true;
            else
                result[i] = false;
            i++;
        }
        
        return result;
    }