并查集题集1 & dfs & bfs & unionMerge & 二分图

0 一些基础

判断整个图是否连通

使用dfs判断整个图是否连通:

        // if not connected, return false
        vecctor<int> stack = {0};
        vector<bool> vis(graph.size(), false);
        vis[0] = true;
        int visCnt = 1;
        // dfs to check if connected
        while(!stack.empty()) {
            int top = stack.back();
            bool allVisited = true;
            for(int i = 0; i < graph[top].size(); ++i) {
                if(!vis[graph[top][i]]) {
                    stack.emplace_back(graph[top][i]);
                    vis[graph[top][i]] = true;
                    allVisited = false;
                    visCnt++;
                    break;
                }
            }
            if(allVisited) {
                stack.pop_back();
            }
        }

        if(visCnt != n) return false;

使用bfs也是可以的,比如下面的0684-冗余链接

并查集的使用

主要是将有关联的边聚合到同一个root里去,可以压缩路径加速find过程

    int find(vector<int>& parent, int curNode) {
        while(parent[curNode] != curNode) {
            parent[curNode] = parent[parent[curNode]];
            curNode = parent[curNode];
        }
        return curNode;
    }

    void unionMerge(vector<int>& parent, int from, int to) {
        int x = find(parent, from);
        int y = find(parent, to);
        
        if(x != y) {
            parent[x] = y;
        }
    }

二分图判断

  • 1 普通思路
    使用bfs遍历,考虑奇偶层级,奇层级为节点集合A,偶层级为节点集合B,最后扫描一遍所有的边,判断是否有边位于AB而不是横跨AB的,
    有的话返回false,不然则true

  • 2 并查集

  • 3 dfs

实例讲解

0785 是否二分图

1 题目

https://leetcode-cn.com/problems/is-graph-bipartite/

2 解题思路

  • 1 普通思路
    使用bfs遍历,考虑奇偶层级,奇层级为节点集合A,偶层级为节点集合B,最后扫描一遍所有的边,判断是否有边位于AB而不是横跨AB的,
    有的话返回false,不然则true;
    同时注意邻接表的判空,所有边个数为0为空的图,是可以二分的哦!
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        
        int edgeNum = 0;
        for(int u = 0; u < n; ++u) {
            for(int v = 0; v < graph[u].size(); ++v) {
                ++edgeNum;
            }
        }
        if(edgeNum == 0) return true;

        // if not connected, return false
        vector<int> stack = {0};
        // vector<bool> vis(graph.size(), false);
        // vis[0] = true;
        // int visCnt = 1;
        // // dfs to check if connected
        // while(!stack.empty()) {
        //     int top = stack.back();
        //     bool allVisited = true;
        //     for(int i = 0; i < graph[top].size(); ++i) {
        //         if(!vis[graph[top][i]]) {
        //             stack.emplace_back(graph[top][i]);
        //             vis[graph[top][i]] = true;
        //             allVisited = false;
        //             visCnt++;
        //             break;
        //         }
        //     }
        //     if(allVisited) {
        //         stack.pop_back();
        //     }
        // }

        // if(visCnt != n) return false;

        // bfs to judge biPartitable
        deque<int> q = {};


        vector<bool> vis2(graph.size(), false);
            unordered_set<int> biPart1 = {};
            unordered_set<int> biPart2;
            deque<int> level = {};
        int bfsNum = 0;
        
        while(bfsNum != n) {        

            for(int i = 0; i < n; ++i) {
                if(!vis2[i]) {
                    q.emplace_back(i);
                    level.emplace_back(0);
                    biPart1.insert(i);
                    ++bfsNum;
                    vis2[i] = true;
                    break;
                }
            }
            while(!q.empty()) {
                int front = q.front();
                for(int i = 0; i < graph[front].size(); ++i) {
                    if(!vis2[graph[front][i]]) {
                        q.emplace_back(graph[front][i]);
                        ++bfsNum;
                        level.emplace_back(level.front() + 1);
                        if(level.front() % 2 == 0) {
                            biPart2.insert(graph[front][i]);
                        } else {
                            biPart1.insert(graph[front][i]);
                        }
                        vis2[graph[front][i]] = true;          
                    }
                }
                q.pop_front();
                level.pop_front();
            }
            // for(auto& i : biPart1) {
            //     std::cout << i << " ";
            // }
            // cout << endl;
            // for(auto& i : biPart2) {
            //     std::cout << i << " ";
            // }
            // cout << endl;
            
            for(int u = 0; u < n; ++u) {
                for(int v = 0; v < graph[u].size(); ++v) {
                    if((biPart2.count(u) == 1 && biPart2.count(graph[u][v]) == 1) || \
                    (biPart1.count(u) == 1 && biPart1.count(graph[u][v]) == 1)) {
                        return false;
                    }
                }
            }
        }


        return true;
    }
}

0765minSwapsCouple

1 题目

https://leetcode-cn.com/problems/couples-holding-hands/

2 解题思路

  • 0 一句话:找连通子图,每个连通子图节点数-1之和即为结果
  • 1 普通思路
    对于每一个2k - 2, 2k - 1的连续两个座位去找,2k - 2上的人的情侣,把它换到2k - 1位置上,遍历k即可 o(n**2)
  • 2 改进思路
    考虑到这样一个事实:
    如果有8个座位,然后所有情侣都没办法相邻而坐,则考虑:将在2k-2和2k-1座位上的相邻两人但不是情侣创建一条边,节点则是情侣的cp序号
    (比如4,5序号的情侣对应一个节点,为5/2 == 4/2 == 2)
    然后我们可以知道,这个图只有一个连通子图,然后其节点数量为4,那么需要交换的次数为4-1 = 3,

容易被迷惑的地方: 一次交换至少能够完成一对情侣,只有最后的一次交换能够完成两队情侣,其余均只能完成一次
所以说这个最小交换次数,其实别反复换,算出来的就是最小的

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        // 容易被迷惑的地方: 一次交换至少能够完成一对情侣,只有最后的一次交换能够完成两队情侣,其余均只能完成一次
        // 所以说这个最小交换次数,其实别反复换,算出来的就是最小的
        
        // 首先注意到,将2个情侣看成一个节点,如果不属于一对的情侣坐在2k - 2, 2k - 1的两个位置上,则连一条线
        vector<int> parent(row.size() / 2);
        for(int i = 0; i < row.size() / 2; ++i) {
            parent[i] = i;
        }

        for(int i = 0; i < row.size(); i += 2) {
            int nodeIdx = i / 2;
            unionMerge(parent, row[i] / 2, row[i + 1] / 2);
            // std::cout << row[i] / 2<< " -> " << row[i + 1] / 2 << std::endl;
        }

        // 找出上图所有连通子图, 所有连通子图的边的节点个数减去1得到一个子图所有情侣相邻而坐需要的交换次数
        unordered_map<int, int> rootIdxToCnt;
        for(int i = 0; i < row.size() / 2; ++i) {
            rootIdxToCnt[find(parent, i)] ++;
            // std::cout << i << " -> " << find(parent, i) << std::endl;
        }

        int res = 0;
        for(auto& it : rootIdxToCnt) {
            res += it.second - 1;
        }
        return res;

    }

    int find(vector<int>& parent, int curNode) {
        while(parent[curNode] != curNode) {
            parent[curNode] = parent[parent[curNode]];
            curNode = parent[curNode];
        }
        return curNode;
    }

    void unionMerge(vector<int>& parent, int from, int to) {
        int x = find(parent, from);
        int y = find(parent, to);
        
        if(x != y) {
            parent[x] = y;
        }
    }
}

0684 冗余链接

1 题目描述

https://leetcode-cn.com/problems/redundant-connection

2 解题思路

使用并查集,将每一条边都看做一个子树,然后一条边一条边加入这个树,当加入的边的两个顶点属于同一个子树时,就认为有回环,则返回这个冗余边。
见如下代码:

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        tree.resize(edges.size() * 2 + 1, -1);
        subTreeSize.resize(edges.size() * 2 + 1, 1);
        
        vector<int> res;
        for(auto& c : edges) {
            if(!unionMerge(c[0], c[1], tree)) {
                res = c;
                break;
            }
        }
        return res;
    }
    
    int find(int tar, vector<int>& tree) {
        int curFather = tree[tar];
        if (curFather < 0) { // tar has no father, so he is the root
            tree[tar] = tar;
            return tar;
        }
        if(tar != curFather) {
            tree[tar] = find(curFather, tree); // compress the data path
        }
        return tree[tar];
    }
    
    
    bool unionMerge(int x, int y, vector<int>& tree) {
        int fx = find(x, tree);
        int fy = find(y, tree);
        if(fx == fy) {
            return false; // x, y are in the same tree, need no merge
        }
        if(subTreeSize[fx] >= subTreeSize[fy]){ // merge by rank of the sub Tree
            tree[fy] = fx;
            subTreeSize[fx] += subTreeSize[fy];
        } else {
            tree[fx] = fy;
            subTreeSize[fy] += subTreeSize[fx];
        }
        return true;
    }
    
    vector<int> subTreeSize;
    vector<int> tree;
};
上一篇:攻防世界Web_mfw


下一篇:Git 基础(3)| 线上bug的处理-分支的新建与合并