leetcode841 钥匙和房间

  1. //v1.0 深度优先搜索
  2. class Solution {
  3.     boolean[] visited;
  4.     int num=0;
  5.     public boolean canVisitAllRooms(List<List<Integer>> rooms) {
  6.         int size = rooms.size();
  7.         visited = new boolean[size];
  8.         dfs(rooms,0);
  9.         return size==num;
  10.     }
  11.     public void dfs(List<List<Integer>> rooms, int room){
  12.         visited[room] = true;
  13.         num++;
  14.         for(int i:rooms.get(room)){
  15.             if(!visited[i]){
  16.                 dfs(rooms,i);
  17.             }
  18.         }
  19.     }
  20. }
  21. //v2.0 广度优先搜索
  22. class Solution {
  23.     public boolean canVisitAllRooms(List<List<Integer>> rooms) {
  24.         int roomNum =  rooms.size();
  25.         int num=0;
  26.         boolean[] visited = new boolean[roomNum];
  27.         Queue<Integer> queue = new LinkedList<Integer>();
  28.         queue.offer(0);
  29.         visited[0] = true;
  30.         while(!queue.isEmpty()){
  31.             int size = queue.size();
  32.             for(int i=0;i<size;i++){
  33.                 num++;
  34.                 int temp = queue.poll();
  35.                 for(int room:rooms.get(temp)){
  36.                     if(!visited[room]){
  37.                         visited[room] = true; 
  38.                         queue.offer(room);
  39.                     }
  40.                 }     
  41.                 }
  42.             }  
  43.             return roomNum == num;          
  44.         }
  45. }