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;
}

1953번: 팀배분

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

$O(n)$

dfs를 통해 홀수 번째 방문시 1, 짝수 번째 방문시 2로 표시한다.

#include<cstdio>
#include<vector>
using namespace std;
int n, c[101], cnt[3];
vector<int> adj[101];
void f(int h, int s) {
        if (c[h]) return;
        c[h] = s;
        cnt[s]++;
        for (auto it : adj[h]) f(it, 3 - s);
}
int main() {
        scanf("%d", &n);
        for (int i = 1, m, x; i <= n; i++)
            for (scanf("%d", &m); m--;) scanf("%d", &x), adj[i].push_back(x);
        for (int i = 1; i <= n; i++) f(i, 1);
        printf("%d\n", cnt[1]);
        for (int i = 1; i <= n; i++) if (c[i] == 1) printf("%d ", i);
        printf("\n%d\n", cnt[2]);
        for (int i = 1; i <= n; i++) if (c[i] == 2) printf("%d ", i);
        return 0;
}

13265번: 색칠하기

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


$O(t(n+m))$

홀수 개수의 노드로 이루어진 사이클이 존재하면 불가능, 그러한 사이클이 존재하지 않는다면 가능하다.

#include<cstdio>
#include<vector>
using namespace std;
int t, n, m, ck[1001], r;
vector<int> adj[1001];
void f(int h) {
    for (auto it : adj[h]) {
        if (!ck[it]) ck[it] = 3 - ck[h], f(it);
        if (ck[h] == ck[it]) r = 1;
    }
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) adj[i].clear(), ck[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 (!ck[i]) ck[i] = 1, f(i);
        puts(r ? "impossible" : "possible");
    }
    return 0;
}