Keys and Rooms

1package pkg5leetcode.official75;2 3/*4 * Keys and Rooms | LC 8415 * APPROACH: DFS from room 0 through key graph.6 * COMPLEXITY: Time O(n+E), Space O(n)7 */8import java.util.*;9 10public class official75_LC841KeysAndRooms {11    static boolean canVisitAllRooms(List<List<Integer>> rooms) {12        boolean[] seen = new boolean[rooms.size()];13        dfs(0, rooms, seen);14        for (boolean v : seen) if (!v) return false;15        return true;16    }17 18    static void dfs(int room, List<List<Integer>> rooms, boolean[] seen) {19        seen[room] = true;20        for (int key : rooms.get(room))21            if (!seen[key]) dfs(key, rooms, seen);22    }23 24    public static void main(String[] args) {25        check(canVisitAllRooms(Arrays.asList(26                Arrays.asList(1), Arrays.asList(2), Arrays.asList(3), Arrays.asList())), "case1");27        check(!canVisitAllRooms(Arrays.asList(28                Arrays.asList(1,3), Arrays.asList(3,0,1), Arrays.asList(2), Arrays.asList(0))), "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}