[Algorithm]Baekjoon 1707번 : 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

using namespace std;
 
vector<vector<int>> graph;
int check[20001];
 
bool DFS(int vertex, int color)
{
    for (int i = 0; i < graph[vertex].size(); i++)
    {
        int nextVertex = graph[vertex][i];
        if (check[nextVertex] == color) return false;
        if (check[nextVertex]) continue;
        check[nextVertex] = color * -1;
        if (DFS(nextVertex, color * -1)) continue;
        else return false;
    }
 
    return true;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int tk = 0;
    int vc = 0;
    int ec = 0;
    int a = 0;
    int b = 0;
 
    cin >> tk;
 
    for (int i = 0; i < tk; i++)
    {
        cin >> vc >> ec;
 
        graph.assign(vc,vector<int>(0));
        memset(check, 0, sizeof(check));
        bool answer = true;
 
        for (int i = 0; i < ec; i++)
        {
            cin >> a >> b;
            graph[a-1].push_back(b-1);
            graph[b-1].push_back(a-1);
        }
 
        for (int i = 0; i < vc; i++)
        {
            if (!check[i])
            {
                check[i] = true;
 
                if (!DFS(i,1))
                {
                    answer = false;
                    break;
                }
            }
        }
 
        if (answer) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
}

이분그래프의 예제문제이다.

각 정점은 이웃한 정점과 반드시 다른색이여야 한다.

 

그렇기 때문에 DFS로 탐색하려 할 경우, 연결된 인접노드를 체크할 때 같은색으로 이미 칠해져있으면 넘기고 값이 0인것,즉 아직 색을 칠하지 않은 정점에 대해서만 탐색을 진행한다.

 

BFS로 탐색하려 할 경우, 같은 depth의 정점들은 모두 같은색이여야한다. (트리형태를 떠올리면 된다.)

그러니 새로운 노드를 만들어 큐에 넣어줄 때 새로운 노드들은 다 같은색이여야한다.

 

일단 이번 문제같은 경우는, 테스트케이스에 연결그래프,비연결그래프 둘 다 포함이 되어있다.

즉 하나의 테스트케이스안에서도 집합이 한개거나(연결그래프), 두개 이상일 수 있다(비연결그래프).

그렇기때문에 모든 정점에대해 검사를 진행해야하고 단 하나의 집합이라도 이분그래프가 아니면 "NO"를 출력해주면 된다. 

 

컬러는 1,-1로 표시한다. 그러면 다른 색으로 변경할 때 * -1만 해주면 깔끔하게 표현이 가능하기 때문이다.

if문의 참여부는 0이외의 값은 전부 true인것도 알아두자.