[백준] 13265 색칠하기

13265번: 색칠하기

 

www.acmicpc.net

풀이

DFS를 통해 탐색하면서 색칠이 가능한지 확인하면 된다. 색칠하는 부분에서 1과 2로 색을 구분하였기 때문에 circle[i] = 3 - circle[idx]로 다른 색깔로 색칠해주었다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
bool is_possible;
vector<int> circle;
vector<vector<int>> line;

void dfs(int idx) {
    for (auto i : line[idx]) {
        if (!circle[i]) {
            circle[i] = 3 - circle[idx];
            dfs(i);
        }
        if (circle[idx] == circle[i]) is_possible = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        circle = vector<int>(n + 1);
        line = vector<vector<int>>(n + 1);
        for (int i = 0; i < m; i++) {
            int tmp1, tmp2;
            cin >> tmp1 >> tmp2;
            line[tmp1].push_back(tmp2);
            line[tmp2].push_back(tmp1);
        }
        is_possible = true;
        for (int i = 1; i <= n; i++)
            if (!circle[i]) {
                circle[i] = 1;
                dfs(i);
            }
        if (is_possible) cout << "possible\n";
        else cout << "impossible\n";
    }
}