Leetcode:841. Keys and Rooms

Posted on | Comments: | Views:
Graph DFS

841. Keys and Rooms

题目理解:

给出一个邻接表, 判断是否能遍历所有节点

思路:

非常基本的DFS(深度优先遍历), 当然BFS也可以完成.

  • 1.访问起始节点
  • 2.访问节点数+1
  • 3.从该节点选择一个连通且未访问的节点来访问
  • 4.重复2 3

小结:

本周算法课进行到了图, DFS是图的一种简单的遍历方法.
时间复杂度为 O(|V|+|E|)

Submission Detail:

Detail

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int ans;
    bool isVisited[1010];
    vector<vector<int>> rooms;
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        ans = 0;
        this->rooms = rooms;
        for (int i = 0; i < 1010; ++i) {
            isVisited[i] = false;
        }
        visitRoom(0);
        return ans == rooms.size();
    }
    void visitRoom(int x) {
        // previsit
        ans++;
        isVisited[x] = true;

        // search
        for (auto i:rooms[x]) {
            if (isVisited[i] == false) {
                visitRoom(i);
            }
        }
    }
};