图论第3天----第841题、第463题-Toy模板网

这篇具有很好参考价值的文章主要介绍了图论第3天----第841题、第463题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

# 图论第3天----第841题、第463题

又继续开始修行，把图论这块补上，估计要个5-6天时间。

一、第841题–钥匙和房间

有向图的遍历。dfs遍历3部曲做，思路也较顺----访问过的，就直接返回；没访问过的，就设为true。注意，这里不需要回溯，因为不是找出一条路径来覆盖到所有的节点，而是能覆盖到就行，不要求一条路径来覆盖。

class Solution {
public:
    void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int x){
        if(visited[x]) return;
        visited[x] = true;
        for(int t : rooms[x]){
            dfs(rooms, visited, t);
        }
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        dfs(rooms, visited, 0);
        for(int i=0; i<rooms.size(); i++){
            if(visited[i] == false) return false;
        }
        return true;
    }
};

二、第463题–岛屿的周长

这个题跟dfs三部曲没关系，属于找规律。根据土地的数量、相邻地块的数量，获得最终的结果----num4 - count2;文章来源地址https://www.toymoban.com/news/detail-726573.html

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int num=0;
        int count=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j] == 1){
                    num++;
                    if(i>0 && grid[i-1][j] == 1) count++;
                    if(j>0 && grid[i][j-1] == 1) count++;
                } 
            }
        }
        return num*4 - count*2;
    }
};

到了这里，关于图论第3天----第841题、第463题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！