백준 13265번 색칠하기 C++

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

13265번: 색칠하기

 

dfs로 2개의 색을 번갈아가며 칠하다가 불가능한 경우가 나오면 dfs 종료

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;
bool ans;

vector<vector<int>> graph;
vector<int> colors;

void Dfs(int curr, int currColor) {
    colors[curr] = currColor;
    for (auto next : graph[curr]) {
        if (colors[next] == 0) {
            Dfs(next, (currColor + 1) % 2);
        }
        else {
            if (colors[next] != currColor) continue;
            ans = false;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        ans = true;
        cin >> n >> m;
        graph = vector<vector<int>>(n + 1, vector<int>());
        colors = vector<int>(n + 1, 0);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) {
            if (colors[i] != 0) continue;
            Dfs(i, 0);
        }
        if (ans) cout << "possible\n";
        else cout << "impossible\n";
    }
}