검색 & 도 론785. 판단 이분 도 (20200716)

글 목록

분석

알고리즘 절차:

DFS

BFS

분석 하 다.

그림 속 의 임의의 두 노드 u 와 v 에 대해 그들 사이 에 한 변 이 직접 연결 되 어 있다 면 u 와 v 는 서로 다른 집합 에 속 해 야 한다.

주어진 그림 이 연결 되 지 않 으 면 우 리 는 한 노드 를 선택 하여 빨간색 으로 염색 합 니 다.그 다음 에 우 리 는 전체 그림 을 옮 겨 다 니 며 이 노드 가 직접 연 결 된 모든 노드 를 녹색 으로 염색 한 것 은 이런 노드 가 시작 노드 와 같은 집합 에 속 하지 않 음 을 나타 낸다.우 리 는 이 녹색 노드 들 이 직접 연 결 된 모든 노드 를 빨간색 으로 염색 했다. 이런 식 으로 유추 하면 그림 의 모든 노드 가 염색 되 지 않 을 때 까지.

만약 에 우리 가 염색 에 성공 할 수 있다 면 빨간색 과 녹색의 노드 는 각각 하나의 집합 에 속 하고 이 무방 향 도 는 하나의 이분 도 이다.만약 에 우리 가 염색 에 성공 하지 못 한다 면, 즉 염색 하 는 과정 에서 어느 순간 에 이미 염색 한 노드 를 방 문 했 고, 그 색깔 은 우리 가 염색 해 야 할 색깔 과 다르다 는 것 은 이 무방 향도 가 이분도 가 아니 라 는 것 을 의미한다.

알고리즘 흐름:
(염색법) 우 리 는 한 노드 를 선택 하여 빨간색 으로 염색 하고 이 노드 부터 전체 무방 향 도 를 옮 겨 다 닌 다.

옮 겨 다 니 는 과정 에서 만약 에 우리 가 노드 u 를 통 해 노드 v (즉, u 와 v 가 그림 에서 한 변 이 직접 연결 되 어 있다) 에 옮 겨 다 니 면 두 가지 상황 이 있 을 것 이다. 1.1 v 가 염색 되 지 않 으 면 우 리 는 이 를 uu 와 다른 색 으로 염색 하고 v 가 직접 연 결 된 절 점 을 옮 겨 다 닐 것 이다.1.2 만약 에 v 가 염색 되 고 색깔 이 u 와 같다 면 주어진 무방 향도 가 이분 도가 아니 라 는 것 을 의미한다.우 리 는 직접 빠 져 나 가 false 로 돌아 갈 수 있다.

옮 겨 다 니 기 가 끝 났 을 때 주어진 무방 향도 가 이분 도 라 는 것 을 설명 하고 True 를 답 으로 되 돌려 줍 니 다.

주의: 문제 에서 주어진 무방 향 그림 이 반드시 연결 되 는 것 은 아니 므 로 각 노드 가 염색 되 거나 답 이 False 로 확 정 될 때 까지 여러 번 옮 겨 다 녀 야 합 니 다.매번 옮 겨 다 닐 때마다 우 리 는 염색 되 지 않 은 노드 를 선택 하여 이 노드 와 직접 또는 간접 적 으로 연 결 된 모든 노드 를 염색 합 니 다.
DFS

class Solution {
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;
    vector<int> color;
    bool valid;

public:
    void dfs(int node, int c, const vector<vector<int>>& graph) {
        color[node] = c;
        int cNei = (c == RED ? GREEN : RED);
        for (int neighbor: graph[node]) {
            if (color[neighbor] == UNCOLORED) {
                dfs(neighbor, cNei, graph);
                if (!valid) {
                    return;
                }
            }
            else if (color[neighbor] != cNei) {
                valid = false;
                return;
            }
        }
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        valid = true;
        color.assign(n, UNCOLORED);
        for (int i = 0; i < n && valid; ++i) {
            if (color[i] == UNCOLORED) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }
};

// 2.
class Solution {
public:
    //             dfs，      
    bool dfs(vector<vector<int>>& graph, int now, int c, vector<int>& color) {
        color[now] = c; //   
        c = -c; //       
        for (auto& adj : graph[now]) {
            if (color[adj] == 0) {
                //         
                if (!dfs(graph, adj, c, color))
                    return false;
            } //               
            else if (color[adj] == color[now])
                return false;
        }
        return true;
    }
    //    
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);
        //            dfs
        for (int i = 0; i < n; ++i) {
            if (color[i] == 0 && !dfs(graph, i, 1, color))
                return false;
        }
        return true;
    }
};

BFS

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;
                // bfs        
                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;
    }
};