C++刷题之旅（46）

LeetCode算法入门（第四十六天） 图 997.找到小镇的法官

信任关系可以用有向图表示，所以法官既是图中入度为 n − 1 n-1 n−1出度为0的点。

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegress(n+1);   //因为从1开始编号
        vector<int> outDegress(n+1);

        for(auto& edge : trust){
            int x = edge[0]; int y = edge[1];  //x->y的边
            ++inDegress[y];  //y的入度+1
            ++outDegress[x];  //x的出度+1
        }

        for(int i = 1; i <= n; ++i){
            if(inDegress[i] == n-1 && outDegress[i] == 0){    //当一个节点的入度为n-1,出度为0时，则他就是法官
                return i;
            }
        }
        return -1;
    }
};

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

入度为0的点，必须包含在结果点集，入度不为0的点，总可以通过一个入度为0的点到达
有向图中，一个节点的入度等于以该节点为终点的有向边的数量，因此一个节点的入度为零，当且仅当对于任何有向边，该节点都不是有向边的终点。

因此，可以遍历所有的边，使用集合存储所有有向边的终点，集合中的所有节点即为入度不为零的节点，剩下的所有节点即为入度为零的节点。

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> ans;
        unordered_set<int> endSet;
        for(auto edge : edges){
            endSet.insert(edge[1]);  //将每条边的终点元素(即入度不为0的节点)插入哈希表中
        }
        for(int i = 0; i < n; i++){
            if(endSet.find(i) == endSet.end()){
                ans.push_back(i);   //将入度为0的元素存进结果集合中
            }
        }
        return ans;
    }
};

钥匙和房间

用深度优先搜索的方式遍历整张图，统计可以到达的节点个数，并标记当前节点是否访问过，以防止重复访问。

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();
        vis.resize(n);
        num = 0;
        dfs(rooms, 0);
        return num == n;
    }
};