Leetcode 刷题笔记-Leetcode 101 第15章 图

Leetcode 刷题笔记-Leetcode 101 第15章 图

图

二分图

二分图算法也称为染色法，是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么图为二分。

Leetcode 785

判断一个图是不是二分图

class Solution {
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;
    vector<int> color;
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, UNCOLORED);
        for (int i = 0; i < n; ++i) {
            if (color[i] == UNCOLORED) {
                queue<int> q;
                q.push(i);
                color[i] = RED;
                while (!q.empty()) {
                    int node = q.front();
                    int cNei = (color[node] == RED ? GREEN : RED);
                    q.pop();
                    for (int neighbor: graph[node]) {
                        if (color[neighbor] == UNCOLORED) {
                            q.push(neighbor);
                            color[neighbor] = cNei;
                        }
                        else if (color[neighbor] != cNei) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

分析：广度优先遍历，需要判断

错误：想简单了

拓扑排序

拓扑排序（topological sort）是一种常见的，对有向无环图排序的算法。给定有向无环图中的N个节点，我们把它们排序成一个线性序列；若原图中节点i指向节点j，则排序结果中i一定在j之前。拓扑排序的结果不是唯一的，只要满足以上条件即可。

Leetcode 210

给定N个课程和这些课程的前置必修课，求可以一次性上完所有课的顺序。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> result;
        vector<int> indegree(numCourses,0);
        vector<vector<int>> graph(numCourses,vector<int>(numCourses,0));
        int m = prerequisites.size();
        for(int i=0;i<m;++i){
            graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
            ++indegree[prerequisites[i][0]];
        }
        while(1){
            if(result.size() == numCourses){
                return result;
            }
            int sign = 0;
            for(int i=0;i<numCourses;++i){
                if(indegree[i] == 0){
                    indegree[i] = -1;
                    result.push_back(i);
                    sign = 1;
                    for(int j=0;j<numCourses;++j){
                        if(graph[i][j] == 1){
                            graph[i][j] = 0;
                            --indegree[j];
                        }
                    }
                }
            }
            if(sign == 0){
                break;
            }
        }
        result.clear();
        return result;
    }
};

分析：经典拓扑排序

错误：有一点小错误，基本一遍AC

练习

Leetcode 1059

付费题目

Leetcode 1135

付费题目

Leetcode 882

经典的节点最短距离问题

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        // 先构建图
        vector<vector<pair<int, int>>> graph(n);
        for (vector<int>& edge : edges)
        {
            int s = edge[0];
            int e = edge[1];
            int cnt = edge[2];
            graph[s].emplace_back(e, cnt);
            graph[e].emplace_back(s, cnt);
        }

        // 保持一个从起点到当前点的距离
        unordered_map<int, int> distances;
        distances[0] = 0;
        for (int i = 1; i < n; ++i)
        {
            distances[i] = maxMoves + 1;
        }

        // 点到点的“额外扩展距离”，最大是cnt
        // 二维变一维 int<<32 + int
        unordered_map<long, int> extras;

        // 结果记录
        int res = 0;

        // 从起点到改点的距离的小顶堆
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int, int>>> q;
        q.push({0, 0});

        while (!q.empty())
        {
            int dist = q.top().first;
            int curr = q.top().second;
            q.pop();
          
            // 忽略更大的距离
            if (dist > distances[curr])
            {
                continue;
            }

            distances[curr] = dist;
            ++res;

            for (auto& pair : graph[curr])
            {
                int next = pair.first;
                int cnt = pair.second;
                // 这里取最小的距离, 取（cnt和 maxMoves-dist）的最小值
                extras[((long)curr << 32) + next] = min(cnt, maxMoves - dist);

                // 计算基于当前点到下一个结点的距离,额外走一步，如果找到更小，则插入队列里
                int dist2 = dist + cnt + 1;
                if (dist2 < distances[next])
                {
                    q.emplace(dist2, next);
                    distances[next] = dist2;
                }
            }
        }

        // 最后加上“额外扩展距离”
        for (vector<int>& edge : edges)
        {
            int s = edge[0];
            int e = edge[1];
            res += min(edge[2], extras[((long)s<< 32) +e] + extras[((long)e<<32) +s]);
        }

        return res;
    }
};

总结

各种高级用法，还比较简单，但是应该不是很常见