1707번: 이분 그래프

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


$O(t(v+e))$

두 가지 색으로 채색이 가능한지 본다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, m, c[20001], r;
vector<int> adj[20001];
void dfs(int h) {
    for (auto it : adj[h]) {
        if (c[it]) r |= c[it] + c[h] != 3;
        else c[it] = 3 - c[h], dfs(it);
    }
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) adj[i].clear(), c[i] = 0;
        for (int i = 0, x, y; i < m; i++) {
            scanf("%d%d", &x, &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        r = 0;
        for (int i = 1; i <= n; i++) if (!c[i]) c[i] = 1, dfs(i);
        puts(r ? "NO" : "YES");
    }
    return 0;
}