[백준]BOJ #2051: 최소 버텍스 커버

작성일 | In

문제 출처: https://www.acmicpc.net/problem/2051

문제 분석

이전에 1867번 문제에서 쾨닉의 정리를 본 적이 있다. 이 정리의 증명은 직접 minimum vertex cover를 구하기에 이를 참고했다.

풀이

이분 그래프를 \(G=(V, E)\) 라 하고 좌, 우를 각각 \(L, R\) 이라고 하자. 그리고 \(L\) 에서 unmatched인 정점이거나 그 정점으로부터 alternating path(후술) 를 이루는 정점들의 집합을 \(Z\) 라고 할 때, minimum vertex cover 집합 \(K\) 는 다음와 같다. \(K=(L\setminus Z) \cup (R \cap Z)\) 따라서 \(Z\) 를 구해주면 되겠다.

*Alternating path : 아래 그림처럼 Unmatched 정점에서 시작하여 match에 이용된 간선, 이용되지 않은 간선을 번갈아가며 방문하는 길이다.

Unmatched bipartite graph

​ Unmatched bipartite graph

Random initial matching , (M), of Graph 1 represented by the red edges

​ Random initial matching M (red)

An alternating path in Graph 1 is represented by red edges, in (M), joined with green edges, not in (M).

​ An alternating path (red & green)

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
int N, M;
vector<int> e[MAX];
int rev[MAX], fo[MAX], visited[MAX], d_visited[MAX];
set<int> leftX, rightX;

void init(){
    cin>>N>>M;
    foi(N){
        int cnt, vtx;
        cin>>cnt;
        while(cnt--){
            cin>>vtx;
            e[i].push_back(vtx);
        }
    }
}
int match(int v){
    for(int d:e[v]){
        if(visited[d]) continue;
        if(rev[d]){
            visited[d]=1;
            if(match(rev[d])){ 
                rev[d]=v;
                fo[v]=d;
                return 1;
            }
        } 
        else{
            rev[d]=v;
            fo[v]=d;
            return 1;
        }
    }
    return 0;
}
int bipartiteMatching(){
    memset(rev, 0, sizeof(rev));
    memset(fo, 0, sizeof(fo));    
    int cnt=0;
    foi(N){
        memset(visited, 0, sizeof(visited));
        if(match(i)) cnt++;
    }
    return cnt;
}
void dfs(int u){
    if(leftX.find(u)!=leftX.end()) return;
    leftX.insert(u);
    for(auto v:e[u]){
        if(d_visited[v]) continue;
        if(rev[v]==u) continue;
        rightX.insert(v);
        d_visited[v]=1;
        dfs(rev[v]);
    }
}
void getMinVtxCover(){
    memset(d_visited, 0, sizeof(d_visited));
    foi(N)
        if(fo[i]==0)
            dfs(i);

    vector<int> leftCover;
    foi(N)
        if(leftX.find(i)==leftX.end()) leftCover.push_back(i);
    
    //print
    cout<<leftCover.size()<<' ';
    for(auto e:leftCover) cout<<e<<' ';
    cout<<endl;
    cout<<rightX.size()<<' ';
    for(auto e:rightX) cout<<e<<' ';
}
void solve(){
    cout<<bipartiteMatching()<<endl;
    getMinVtxCover();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    init(); 
    solve();
}

Reference