[LeetCode] 785. Is Graph Bipartite?

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

Is Graph Bipartite? - LeetCode

문제 유형 : DFS / BFS
문제 난이도 : Medium
 
문제
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected).
• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
Return true if and only if it is bipartite.
 
n개의 노드를 가진 무방향 그래프가 주어진다. 
그래프의 노드들이 두 독립된집합 A와 B로 나누어지고, 서로 다른 집합끼리만 이어지는 그래프인 경우를 이분 그래프라고 할 때,
이분 그래프이면 true를, 아니면 false를 반환하라.
 
풀이

DFS / BFS로 문제를 풀면 된다. 탐색을 하는 과정에 위 그림과 같이 현재 노드의 색깔이 인접 노드의 색깔과 같은 경우 조건을 불만족하므로 false를 반환시키면 된다.
탐색을 마치면 true를 반환해주면 된다. 시간 복잡도는 O(V+E).
 
코드(C++)

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);

        for(int node = 0; node < n; node++){
            if(color[node] != 0) continue;

            queue<int> q;
            q.push(node);
            color[node] = 1;

            while(!q.empty()){
                int cur = q.front();
                q.pop();

                for(int ne : graph[cur]){
                    if(color[ne] == 0){
                        color[ne] = -color[cur];
                        q.push(ne);
                    }else if(color[ne] != -color[cur]){
                        return false;
                    }
                }
            }
        }

        return true;
    }
};