Possible Bipartition

n 명이 있을 때 사람들을 2개의 그룹으로 나눌 수 있는지 판단하는 문제

여기서 조건이 있는데 같은 그룹으로 묶을 수 없는 사람들이 들어 있는 2차원 벡터를 받는다.

class Solution {
public:
    static const int COLOR{8};

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        
        vector<vector<int>> graph(n);

        for (int i = 0; i < dislikes.size(); i++)
        {
            graph[dislikes[i][0] - 1].push_back(dislikes[i][1] - 1);
            graph[dislikes[i][1] - 1].push_back(dislikes[i][0] - 1);
        }

        vector<int> colored(n);
        for (int i = 0; i < n; i++)
        {
            if (colored[i] == 0 && SearchDFS(i, COLOR, colored, graph) == false)
            {
                return false;
            }
        }

        return true;
    }

    bool SearchDFS(int &index, int color, vector<int> &colored, vector<vector<int>> &graph)
    {
        colored[index] = color;

        for (int i = 0; i < graph[index].size(); i++)
        {
            int nextIndex{graph[index][i]};
            if (colored[nextIndex] != 0)
            {
                if (colored[nextIndex] == color)
                {
                    return false;
                }
                continue;
            }

            if (SearchDFS(nextIndex, color ^ 1, colored, graph) == false)
            {
                return false;
            }
        }

        return true;
    }
};