lcGraphUndirected1 - 无向图题集1

Posted on Edited on

0 一些基础

判断整个图是否连通

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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为空的图，是可以二分的哦！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    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，

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    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 解题思路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
};