Leetcode 图 3题

A了三道图的题目，基本上都是有向图，个人感觉图的数据结构不像树和链表那样直观，目前刷的三道题目基本上都是以数组的形式体现，基本上都是二维数组，接下来的三道题目用到了一点点图论和搜索算法

题目出自leetcode

1. 997 找到小镇的法官

https://leetcode-cn.com/problems/find-the-town-judge/

1） 题目描述与输入样例

2）题目解读与思路

题目要求判断是否存在法官，而法官是不相信任何人，其他人则是相信法官的，所以容易分析出法官这一节点的入度为 n - 1， n为总人数， 而出度为 0；

这里的出度和入度可以理解为，一个节点出去的路径数，和进来该节点的路径数。

由于法官的出度为0，所以一般情况下需要两个数组分别去存储节点的出度和入度的方法就可以变为只用一个数组——度差数组来纪录每个节点的度差
度 差 = 入 度 − 出 度 度差 = 入度 - 出度 度差=入度−出度
而法官的度差则为 n-1

3）code

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // 有向图，cnt数组记录每个点的出度入度
        // 当有一个入度为 n -1时即为答案
        int cnt[n + 1];
        // 长度为 n + 1是因为n个人，他们的编号从1 到n，0位可不考虑
        memset(cnt, 0, sizeof(int) * (n + 1));
        for(vector<int>& t : trust)
        {
            // 入度，度差+1
            cnt[t[0]]--;
            // 出度， 度差-1
            cnt[t[1]]++;
        }
        for(int i = 1; i <= n; ++i)
        {
            
            if(cnt[i] == n - 1)
            {
                return i;
            }
        }
        return -1;
    }
};

2. 1557 可以到达所有点的最少数目

1）题目描述与输入样例

2）题目解读与思路

题目保证了一定存在一个最小点集，使得有了这些点就可以走遍图中所有的节点

那么对于一个点对[s, e] s为起点，e为终点，s可以通过s->e， 再去遍历以e为起点的路径

那么所谓的最小点集， 其实就是图中只作为起点的点的集合，比如示例1中的 0 和 3

那么题目就变成了，找到图中所有出度为 0的节点

3）code

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        // 入度为0的点集
        vector<int> ans;
        vector<int> cnt(n, 0);
        for(auto e : edges)
        {
            // 入度增加
            cnt[e[1]]++;
        }
        // 遍历每个节点的入度
        for(int i = 0; i < n; ++i)
        {
            if(cnt[i] == 0)
            {
                // 入度为0的节点存入数组
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

3. 841 钥匙和房间

1）题目描述与输入样例

2）题目解读与思路

题目是要判断给出的二位点集（也就是图），能不能全部都走到。这里有一个陷阱，写了上边两道沾了点图论的题目，不讲思索的会想到，这题其实可以把房间的索引视为起点，房间里的钥匙视为终点，只需遍历图，除了0号房间外判断入度是否为0即可，如果出现除0号的房间外的入度为0，则该房间一定走不了

但是样例2告诉我们这个思路是不行的，每个房间的编号都有，但是进入不了2号房间。

所以这题，我们需要使用搜索算法

怎样算能够进入所有房间？

计算我们可以进入的房间数，如果可以进入的房间数 == 给定房间数，那么就算成功

同时为了防止重复遍历房间，不妨多设置一个数组用来判断该房间是否被访问

3）code

dfs

class Solution {
public:
    vector<int> vis;
    int num;
    void dfs(vector<vector<int>>& rooms, int x)
    {
        vis[x] = true;
        num++;
        for(auto& it : rooms[x])
        {
            if(!vis[it])
            {
                dfs(rooms, it);
            }
        }
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        num = 0;
        vis.resize(n);
        dfs(rooms, 0);
        return num==n;
    }
};

bfs

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        // 记录节点的入度
        // 除了节点0之外的所有节点中存在入度为0的节点则false
        // 否则即为true
        int n = rooms.size();
        vector<int> cnt(n, 0);
        for(vector<int> room : rooms)
        {
            for(int r : room)
            {
                // 每一个房间的钥匙号——对应的节点
                cnt[r]++;
            }
        }
        // 只需从 节点1开始即可
        for(int i = 1; i < n; ++i)
        {
            if(cnt[i] == 0)
            {
                return false;
            }
        }
        return true;
    }
};