[13265번] 색칠하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

2. BFS :: http://www.crocus.co.kr/521

이 문제는 이분 그래프로 표현 할 수 있는가? 라는 문제이다.

즉, 이분 매칭을 해라 라는 문제가 아니고 이러한 그래프는 이분 그래프로 표현 할 수 있는가를 묻는 것이다.

이분 그래프로 표현 할 수 있다는 의미는 각 정점들을 A 그룹 B 그룹으로 정확히 나눌 수 있어야 한다는 의미가 된다.

결국 BFS로 생각하면 이분 그래프가 되는지 안되는지 알 수 있다.

시작점을 잡고 그 점부터 시작해서 한칸씩 가며 1또는 -1로 색칠을 해주고 만약 이미 색칠되어있는 부분을 만났을 때 

그 부분이 현재 정점의 색과 같다면 이분 그래프가 될 수 없다는 것이다는 것을 이용한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++)
    {
        int V, E;
        scanf("%d %d", &V, &E);
 
        vector<int> vc[1002];
        vector<bool> visit(1002, false);
        vector<int> color(1002);
 
        for (int i = 0; i < E; i++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
 
            vc[from].push_back(to);
            vc[to].push_back(from);
        }
 
        int palette;
        bool chk = true;
 
        for (int i = 1; i <= V; i++)
        {
            if (visit[i])
                continue;
 
            queue<int> q;
 
            q.push(i);
 
            while (!q.empty())
            {
                int here = q.front();
 
                q.pop();
 
                if (visit[here])
                    continue;
 
                visit[here] = true;
                if (color[here] == 0)
                {
                    color[here] = 1;
                    palette = -1;
                }
                else if (color[here] == 1)
                    palette = -1;
 
                else if (color[here] == -1)
                    palette = 1;
 
                for (int i = 0; i < vc[here].size(); i++)
                {
                    int next = vc[here][i];
                    if (color[next] != 0 && color[next] == -palette)
                    {
                        chk = false;
                        break;
                    }
                    color[next] = palette;
                    q.push(next);
                }
 
                if (!chk)
                    break;
            }
        }
        chk == true ? printf("possible\n") : printf("impossible\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>