【問題描述】[中等]

【解答思路】

當 xx 號房間中有 yy 號房間的鑰匙時，我們就可以從 xx 號房間去往 yy 號房間。如果我們將這 nn 個房間看成有向圖中的 nn 個節點，那么上述關系就可以看作是圖中的 xx 號點到 yy 號點的一條有向邊。

這樣一來，問題就變成了給定一張有向圖，詢問從 00 號節點出發是否能夠到達所有的節點。

用visit數組或者Set記錄已經訪問的節點

1. DFS

使用深度優先搜索的方式遍歷整張圖，統計可以到達的節點個數，并利用數組 vis 標記當前節點是否訪問過，以防止重復訪問。
復雜度

class Solution {boolean[] vis;int num;public boolean canVisitAllRooms(List<List<Integer>> rooms) {int n = rooms.size();num = 0;vis = new boolean[n];dfs(rooms, 0);return num == n;}public void dfs(List<List<Integer>> rooms, int x) {vis[x] = true;num++;for (int it : rooms.get(x)) {if (!vis[it]) {dfs(rooms, it);}}} }

2. BFS

用廣度優先搜索的方式遍歷整張圖，統計可以到達的節點個數，并利用數組 vis /Set標記當前節點是否訪問過，以防止重復訪問。
復雜度

class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {int n = rooms.size(), num = 0;boolean[] vis = new boolean[n];Queue<Integer> que = new LinkedList<Integer>();vis[0] = true;que.offer(0);while (!que.isEmpty()) {int x = que.poll();num++;for (int it : rooms.get(x)) {if (!vis[it]) {vis[it] = true;que.offer(it);}}}return num == n;} } public boolean canVisitAllRooms(List<List<Integer>> rooms) {Stack<Integer> a = new Stack<>();HashSet<Integer> set = new HashSet<Integer>();set.add(0);a.add(0);while(!a.isEmpty()){int i =a.pop();for(int j:rooms.get(i)){if(!set.contains(j)){a.add(j);set.add(j);if (rooms.size() == set.size()) return true;}}}return (rooms.size() == set.size()) ;}

【總結】

1. DFS 遞歸回溯 BFS 隊列

2.審題！！！ 思考后再行動

轉載鏈接：https://leetcode-cn.com/problems/keys-and-rooms/solution/yao-chi-he-fang-jian-by-leetcode-solution/

總結

以上是生活随笔為你收集整理的[Leetcode][第841题][JAVA][钥匙和房间][DFS][BFS]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。