3204번: 커플 깨기

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


$O(nm)$

문제를 항상 해결할 수 있는 방법을 찾아보자.
모든 노드의 차수가 짝수이면 오일러서킷을 찾아 해결할 수 있다.(간선 방향은 탐색 방향으로 결정된다.)
노드의 차수가 홀수인 것이 존재한다면(이러한 노드의 개수는 항상 짝수이다.) 이러한 노드들을 하나의 더미 노드와 연결하고 오일러 서킷을 찾으면 된다.
오일러 서킷을 찾은 뒤 더미 노드와 연결된 간선을 제거하면 된다, 더미 노드는 단 하나이므로 주어진 조건을 만족한다.
입력데이터에 분리된 그래프가 주어지는 경우도 있으니 유의해서 해결하자.

#include<cstdio>
const int MAX_N = 1e3;
int n, m, adj[MAX_N + 1][MAX_N + 1];
void dfs(int h) {
    for (int i = 0; i <= n; i++) {
        if (!adj[h][i]) continue;
        adj[h][i] = adj[i][h] = 0;
        dfs(i);
        if (h&&i) printf("%d %d\n", h, i);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        adj[x][y] = adj[y][x] = 1;
    }
    for (int i = 1, c; i <= n; i++) {
        c = 0;
        for (int j = 1; j <= n; j++) c += adj[i][j];
        if (c & 1) adj[0][i] = adj[i][0] = 1;
    }
    puts("Yes");
    for (int i = 1; i <= n; i++) dfs(i);
    return 0;
}