LeetCode—图

LeetCode—图

二分图（可以将图中的所有顶点分成两个不想交的集合，使得同一个集合的顶点不相连）
如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。

1、判断是否为二分图
T785. Is Graph Bipartite? (Medium)

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> colors(graph.size());
        for(int i=0; i<graph.size(); ++i){
            if(colors[i] != 0)  continue;
            colors[i] = 1;
            queue<int> q{{i}};
            while(!q.empty()){
                int t = q.front();
                q.pop();
                for(auto a : graph[t]){
                    if(colors[a] == colors[t])  return false;
                    if(colors[a] == 0){
                        colors[a] =-1 * colors[t];
                        q.push(a);
                    }
                }
            }
        }
        return true;

    }
};

拓扑排序
常用于在具有先序关系的任务规划中。

1、课程安排的合法性
T207. Course Schedule (Medium)

vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> in(numCourses);
        for (auto a : prerequisites) {
            graph[a[1]].push_back(a[0]);
            ++in[a[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] != 0) return false;
        }
        return true;

2、课程安排的顺序
T210. Course Schedule II (Medium)

class Solution {
private:
    // 存储有向图
    vector<vector<int>> edges;
    // 存储每个节点的入度
    vector<int> indeg;
    // 存储答案
    vector<int> result;

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }

        queue<int> q;
        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            // 从队首取出一个节点
            int u = q.front();
            q.pop();
            // 放入答案中
            result.push_back(u);
            for (int v: edges[u]) {
                --indeg[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }

        if (result.size() != numCourses) {
            return {};
        }
        return result;
    }
};

并查集
并查集可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。

1、冗余连接
T684. Redundant Connection (Medium)

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        unordered_map<int, unordered_set<int>> m;
        for (auto edge : edges) {
            if (hasCycle(edge[0], edge[1], m, -1)) return edge;
            m[edge[0]].insert(edge[1]);
            m[edge[1]].insert(edge[0]);
        }
        return {};
    }
    bool hasCycle(int cur, int target, unordered_map<int, unordered_set<int>>& m, int pre) {
        if (m[cur].count(target)) return true;
        for (int num : m[cur]) {
            if (num == pre) continue;
            if (hasCycle(num, target, m, cur)) return true;
        }
        return false;


    }
};