当前位置：首页 > article >正文

leetcode 841.钥匙和房间

article 2025/2/5 22:11:49

1.题目要求:
在这里插入图片描述

2.解题思路:
利用图的深度优先搜索进行遍历

3.解题代码:

class Solution {
public:
    void VisitAllRooms(int v_index,vector<vector<int>>&rooms,vector<bool>& visited){
        //把每一次设立的结点都立标志
        visited[v_index] = true;
        for(int j = 0;j < rooms[v_index].size();j++){
            //如果结点使用过，就不需要再进行遍历了
            if(visited[rooms[v_index][j]] != true){
                int index = rooms[v_index][j];
                VisitAllRooms(index,rooms,visited);
            }
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        //设立数组为给已经遍历的结点设立标志
        vector<bool> visited;
        visited.resize(rooms.size(),false);
        int v_index = 0;
        //进行深度优先遍历
        VisitAllRooms(v_index,rooms,visited);
        for(int i = 0;i < visited.size();i++){
            if(visited[i] == false){
                return false;
            }
        }
        return true;
    }
};