Uion find, BFS和DFS三种解法的graph题目类型

缘起：

元素可想成节点，题目会抽象出节点的关联性。由此，本质是graph，如果节点间的关系是相互的，就是无向图。此类型属于无向图，如是有向图，参照indegree变量+queue队列的操作。
分析：
BFS: 建立邻接链表，采用queue，撒网，一层一层的。
DFS:建立邻接矩阵，一串到底。
Union find: 使用hash map建立邻接链表

1596. Possible Bipartition

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Have you met this question in a real interview?  

Example

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Union find
class Solution { public: /** * @param N: sum of the set * @param dislikes: dislikes peoples * @return: if it is possible to split everyone into two groups in this way */ bool possibleBipartition(int N, vector<vector<int>> &dislikes) { // Write your code here. // 很有意思的一题，感觉也不难。就是没有一个能实现的思路。 // 要解法思想 // give up!!!!!!!!! // 昨日看了答案，发现是个图的问题，union find, DFS, BFS都可以解。想起来，之前也有一道类似的题。 // union find dislikes的要分别放在两个group里面。如果发现dislike在一个group里面，就return false. // initial vector<int> roots(N + 1, 0); // build the graph unordered_map<int, vector<int>> hMap; for(auto i : dislikes){ hMap[i[0]].push_back(i[1]);//无向图 hMap[i[1]].push_back(i[0]); / } for(int i = 1; i <= N; i++){ roots[i] = i; } // build the roots for(int i = 1; i <= N; i++){ if(hMap.count(i) == 0){ continue; } int x = find(roots, i); // all i[0]'s dislikes should be in same group vector<int> dis = hMap[i]; int y = find(roots, dis[0]); if(x == y){ return false; } for(int j = 1; j < dis.size(); j++){ int z = find(roots, dis[j]); if(x == z){ return false; } roots[z] = y; } } return true; } int find(vector<int> &roots, int a){ while(roots[a] != a){ a = roots[a]; } return a; } };

BFS
class Solution { public: /** * @param N: sum of the set * @param dislikes: dislikes peoples * @return: if it is possible to split everyone into two groups in this way */ bool possibleBipartition(int N, vector<vector<int>> &dislikes) { // Write your code here. // BFS的解法 // 思路：建立dislike的group, 遍历每个节点时，该节点对应的dislike的节点应该在另一个group.如果和当前节点在一个group，就return false // 例： [1,2] [1,3] [2,3] // 1(color 1) -> [2,3](color -1) (pop出2时，3的color和2一样，所以false) // 例: [1,2] [3,4] [1,3] // 1(color 1) -> [2,3](color - 1), (pop 2 dis是1已经color, pop 3 dis是1和4,1已经color， color 4 as 1)， 所以分组是（1,4） （2,3）true. // 很有意思！！！ vector<vector<int>> graph(N + 1); //build graph for(auto i : dislikes){ graph[i[0]].push_back(i[1]); graph[i[1]].push_back(i[0]); } // define flags vector<int> flags(N + 1, 0); for(int i = 1; i <= N; i++){ if(flags[i] != 0){//have flaged continue; } flags[i] = 1; //flag as 1, group 0 std::queue<int> q; q.push(i); while(!q.empty()){ int tmp = q.front(); q.pop(); for(auto j : graph[tmp]){ if(flags[j] == flags[tmp]){ // conflict, dislikes are in same group return false; } if(flags[j] != 0){ continue; } flags[j] = -flags[tmp]; // flag dis in the other group q.push(j); } } } return true; } };


DFS

class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(N + 1, vector<int>(N + 1));
        for (auto dislike : dislikes) {
            g[dislike[0]][dislike[1]] = 1;
            g[dislike[1]][dislike[0]] = 1;
        }
        vector<int> colors(N + 1);
        for (int i = 1; i <= N; ++i) {
            if (colors[i] == 0 && !helper(g, i, 1, colors)) return false;
        }
        return true;
    }
    bool helper(vector<vector<int>>& g, int cur, int color, vector<int>& colors) {
        colors[cur] = color;
        for (int i = 0; i < g.size(); ++i) {
            if (g[cur][i] == 1) {
                if (colors[i] == color) return false;
                if (colors[i] == 0 && !helper(g, i, -color, colors)) return false;
            }
        }
        return true;
    }
};