UVaOJ)10968 KuPellaKeS

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909

도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다.

연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다.

우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자.

그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나게 되면 답을 만족하게 된다.

하지만 우리는 최소 간선의 개수를 구해야 하므로 그냥 두 도시의 최단거리를 구한다음에 삭제해주면 된다.

두 정점의 최단거리는 BFS를 통하여 구할 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, m, x, y, disc[1010], g[1010], back[1010];
vector<vector<int>> vt;
int bfs(int here) {
    disc[here] = 1;
    queue<int> qu;
    qu.push(here);
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int h = qu.front();
            qu.pop();
            if (h != here&&g[h] % 2) {
                int bt = h;
                while (bt!=here) {
                    g[bt]--;
                    g[back[bt]]--;
                    bt = back[bt];
                }
                return ret;
            }
            for (auto next : vt[h]) {
                if (disc[next])continue;
                if (g[next] % 2 && g[next] >= 3) {
                    qu.push(next);
                    disc[next] = 1;
                    back[next] = h;
                }
                if (!(g[next] % 2) && g[next] >= 4) {
                    qu.push(next);
                    disc[next] = 1;
                    back[next] = h;
                }
                
            }
        }
        ret++;
    }
    return -1;
}
int go() {
    for (int i = 1; i <= n; i++)
        if (g[i] < 2)return -1;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i] % 2) {
            memset(disc, 0, sizeof(disc));
            int f = bfs(i);
            if (f == -1)return -1;
            ret += f;
        }
    }
    return ret;
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (!n&&!m)return 0;
        memset(g, 0, sizeof(g));
        vt.clear();
        vt.resize(n + 1);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &x, &y);
            vt[x].push_back(y);
            vt[y].push_back(x);
            g[x]++, g[y]++;
        }
        int r = go();
        if (r == -1)puts("Poor Koorosh");
        else printf("%d\n", r);
    }
    return 0;
}