König's Theorem

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Bipartite graph: left side [1..nL], right side [1..nR]
5
// Edges are from L to R.
6
struct HopcroftKarp {
7
    int nL, nR;
8
    vector<vector<int>> adj; // adj[u] = list of v in R
9
    vector<int> dist;        // BFS distances for L side
10
    vector<int> matchL, matchR; // matchL[u] in R or 0 if free; matchR[v] in L or 0
11
12
    HopcroftKarp(int nL, int nR) : nL(nL), nR(nR) {
13
        adj.assign(nL + 1, {});
14
        matchL.assign(nL + 1, 0);
15
        matchR.assign(nR + 1, 0);
16
        dist.resize(nL + 1);
17
    }
18
19
    void add_edge(int u, int v) {
20
        // 1 <= u <= nL, 1 <= v <= nR
21
        adj[u].push_back(v);
22
    }
23
24
    bool bfs() {
25
        queue<int> q;
26
        // Initialize layer distances; 0 denotes NIL's level will be set via dist[0]
27
        for (int u = 1; u <= nL; ++u) {
28
            if (matchL[u] == 0) {
29
                dist[u] = 0;
30
                q.push(u);
31
            } else {
32
                dist[u] = -1;
33
            }
34
        }
35
        bool reachableFreeRight = false; // whether we can reach a free vertex on R via alternating path
36
        while (!q.empty()) {
37
            int u = q.front(); q.pop();
38
            for (int v : adj[u]) {
39
                int uu = matchR[v]; // 0 if v is free; otherwise go to its matched left neighbor
40
                if (uu == 0) {
41
                    // Found a shortest path to a free R-vertex
42
                    reachableFreeRight = true;
43
                } else if (dist[uu] == -1) {
44
                    dist[uu] = dist[u] + 1;
45
                    q.push(uu);
46
                }
47
            }
48
        }
49
        return reachableFreeRight;
50
    }
51
52
    bool dfs(int u, vector<int>& it) {
53
        for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
54
            int v = adj[u][i];
55
            int uu = matchR[v];
56
            // If v is free, try to match; otherwise, try to advance along layer graph
57
            if (uu == 0 || (dist[uu] == dist[u] + 1 && dfs(uu, it))) {
58
                matchL[u] = v;
59
                matchR[v] = u;
60
                return true;
61
            }
62
        }
63
        dist[u] = -1; // dead end for this layer
64
        return false;
65
    }
66
67
    int max_matching() {
68
        int matching = 0;
69
        while (bfs()) {
70
            vector<int> it(nL + 1, 0);
71
            for (int u = 1; u <= nL; ++u) {
72
                if (matchL[u] == 0) {
73
                    if (dfs(u, it)) matching++;
74
                }
75
            }
76
        }
77
        return matching;
78
    }
79
80
    // After calling max_matching(), build a minimum vertex cover using alternating BFS
81
    // Rule: Start from all free L vertices, traverse non-matching edges (L->R) and matching edges (R->L)
82
    // Then cover = (L \ Z) U (R ∩ Z)
83
    pair<vector<int>, vector<int>> min_vertex_cover() {
84
        vector<char> visL(nL + 1, false), visR(nR + 1, false);
85
        queue<pair<int,bool>> q; // (id, isLeft)
86
        for (int u = 1; u <= nL; ++u) if (matchL[u] == 0) {
87
            visL[u] = true;
88
            q.push({u, true});
89
        }
90
        while (!q.empty()) {
91
            auto [id, isLeft] = q.front(); q.pop();
92
            if (isLeft) {
93
                int u = id;
94
                for (int v : adj[u]) {
95
                    if (matchL[u] != v && !visR[v]) { // non-matching edge
96
                        visR[v] = true;
97
                        q.push({v, false});
98
                    }
99
                }
100
            } else {
101
                int v = id;
102
                int u = matchR[v];
103
                if (u != 0 && !visL[u]) { // follow matching edge back to L
104
                    visL[u] = true;
105
                    q.push({u, true});
106
                }
107
            }
108
        }
109
        vector<int> coverL, coverR;
110
        for (int u = 1; u <= nL; ++u) if (!visL[u]) coverL.push_back(u); // L \ Z
111
        for (int v = 1; v <= nR; ++v) if (visR[v]) coverR.push_back(v);  // R ∩ Z
112
        return {coverL, coverR};
113
    }
114
};
115
116
int main() {
117
    ios::sync_with_stdio(false);
118
    cin.tie(nullptr);
119
120
    int nL, nR, m; // read bipartite sizes and edges
121
    // Example input format:
122
    // nL nR m
123
    // m lines: u v  (1-based u in [1..nL], v in [1..nR])
124
    if (!(cin >> nL >> nR >> m)) {
125
        // Demo graph if no input
126
        nL = 3; nR = 3; m = 4;
127
        HopcroftKarp hk(nL, nR);
128
        hk.add_edge(1,1);
129
        hk.add_edge(2,1);
130
        hk.add_edge(2,2);
131
        hk.add_edge(3,3);
132
        int mm = hk.max_matching();
133
        auto [cL, cR] = hk.min_vertex_cover();
134
        cout << "max_matching = " << mm << "\n";
135
        cout << "min_vertex_cover_size = " << (cL.size() + cR.size()) << "\n";
136
        cout << "L part:"; for (int u: cL) cout << ' ' << u; cout << "\n";
137
        cout << "R part:"; for (int v: cR) cout << ' ' << v; cout << "\n";
138
        return 0;
139
    }
140
141
    HopcroftKarp hk(nL, nR);
142
    for (int i = 0; i < m; ++i) {
143
        int u, v; cin >> u >> v;
144
        hk.add_edge(u, v);
145
    }
146
    int mm = hk.max_matching();
147
    auto [cL, cR] = hk.min_vertex_cover();
148
149
    cout << mm << "\n"; // size of maximum matching == size of min vertex cover
150
    cout << (cL.size() + cR.size()) << "\n";
151
    // Optionally print the cover itself
152
    // Left side
153
    cout << cL.size(); for (int u : cL) cout << ' ' << u; cout << "\n";
154
    // Right side
155
    cout << cR.size(); for (int v : cR) cout << ' ' << v; cout << "\n";
156
    return 0;
157
}
158

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Simpler but slower matching to emphasize the cover construction
5
struct Kuhn {
6
    int nL, nR;
7
    vector<vector<int>> g; // adj from L to R
8
    vector<int> matchR; // which left is matched to right v (0 if free)
9
    vector<int> seen;   // DFS visited R nodes timestamp
10
    int visToken = 1;
11
12
    Kuhn(int nL, int nR): nL(nL), nR(nR) {
13
        g.assign(nL + 1, {});
14
        matchR.assign(nR + 1, 0);
15
        seen.assign(nR + 1, 0);
16
    }
17
18
    void add_edge(int u, int v) { g[u].push_back(v); }
19
20
    bool dfs(int u) {
21
        for (int v : g[u]) {
22
            if (seen[v] == visToken) continue;
23
            seen[v] = visToken;
24
            if (matchR[v] == 0 || dfs(matchR[v])) {
25
                matchR[v] = u;
26
                return true;
27
            }
28
        }
29
        return false;
30
    }
31
32
    // Returns matchL for completeness
33
    vector<int> max_matching() {
34
        vector<int> matchL(nL + 1, 0);
35
        int flow = 0;
36
        bool progress = true;
37
        while (progress) {
38
            progress = false;
39
            ++visToken;
40
            for (int u = 1; u <= nL; ++u) if (matchL[u] == 0) {
41
                if (dfs(u)) {
42
                    progress = true;
43
                    // Recover the edge to which u was matched in matchR
44
                    // Find v with matchR[v] == u (could optimize by returning it)
45
                    for (int v : g[u]) if (matchR[v] == u) { matchL[u] = v; break; }
46
                    ++flow;
47
                }
48
            }
49
        }
50
        return matchL;
51
    }
52
};
53
54
// Build min vertex cover from L->R adjacency and a maximum matching matchL/matchR
55
pair<vector<int>, vector<int>> build_min_vertex_cover(const vector<vector<int>>& adj, const vector<int>& matchL, const vector<int>& matchR) {
56
    int nL = (int)matchL.size() - 1;
57
    int nR = (int)matchR.size() - 1;
58
    vector<char> visL(nL + 1, false), visR(nR + 1, false);
59
    queue<pair<int,bool>> q;
60
    for (int u = 1; u <= nL; ++u) if (matchL[u] == 0) { visL[u] = true; q.push({u, true}); }
61
    while (!q.empty()) {
62
        auto [id, isLeft] = q.front(); q.pop();
63
        if (isLeft) {
64
            int u = id;
65
            for (int v: adj[u]) if (matchL[u] != v && !visR[v]) { visR[v] = true; q.push({v, false}); }
66
        } else {
67
            int v = id;
68
            int u = matchR[v];
69
            if (u != 0 && !visL[u]) { visL[u] = true; q.push({u, true}); }
70
        }
71
    }
72
    vector<int> cL, cR;
73
    for (int u = 1; u <= nL; ++u) if (!visL[u]) cL.push_back(u);
74
    for (int v = 1; v <= nR; ++v) if (visR[v]) cR.push_back(v);
75
    return {cL, cR};
76
}
77
78
int main() {
79
    ios::sync_with_stdio(false); cin.tie(nullptr);
80
81
    int nL = 4, nR = 4; // small demo
82
    Kuhn solver(nL, nR);
83
    vector<vector<int>> adj(nL + 1);
84
85
    auto add = [&](int u, int v){ solver.add_edge(u,v); adj[u].push_back(v); };
86
    add(1,1); add(1,2); add(2,2); add(3,3); add(3,4); add(4,4);
87
88
    vector<int> matchL = solver.max_matching();
89
    vector<int> matchR(nR + 1, 0);
90
    for (int v = 1; v <= nR; ++v) if (solver.matchR[v] != 0) matchR[v] = solver.matchR[v];
91
92
    auto [cL, cR] = build_min_vertex_cover(adj, matchL, matchR);
93
94
    cout << "matching_size = ";
95
    int mm = 0; for (int u = 1; u <= nL; ++u) if (matchL[u]) ++mm; cout << mm << "\n";
96
    cout << "min_vertex_cover_size = " << (int)(cL.size() + cR.size()) << "\n";
97
    cout << "Cover L:"; for (int u : cL) cout << ' ' << u; cout << "\n";
98
    cout << "Cover R:"; for (int v : cR) cout << ' ' << v; cout << "\n";
99
}
100

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Assume we already computed a min vertex cover (coverL, coverR) on bipartite graph (L,R)
5
// Then a maximum independent set is simply (L \ coverL) U (R \ coverR).
6
int main(){
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9
10
    int nL = 3, nR = 4;
11
    vector<int> coverL = {2};      // example: L-cover has vertex 2
12
    vector<int> coverR = {1, 4};   // example: R-cover has vertices 1 and 4
13
14
    vector<char> inCovL(nL + 1, false), inCovR(nR + 1, false);
15
    for (int u : coverL) inCovL[u] = true;
16
    for (int v : coverR) inCovR[v] = true;
17
18
    vector<int> indepL, indepR; // maximum independent set
19
    for (int u = 1; u <= nL; ++u) if (!inCovL[u]) indepL.push_back(u);
20
    for (int v = 1; v <= nR; ++v) if (!inCovR[v]) indepR.push_back(v);
21
22
    cout << "max_independent_set_size = " << (int)(indepL.size() + indepR.size()) << "\n";
23
    cout << "Independent L:"; for (int u : indepL) cout << ' ' << u; cout << "\n";
24
    cout << "Independent R:"; for (int v : indepR) cout << ' ' << v; cout << "\n";
25
26
    return 0;
27
}
28

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Validate on tiny graphs (nL, nR <= 10) by brute forcing vertex covers
5
int main(){
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8
9
    int nL, nR, m; cin >> nL >> nR >> m;
10
    if (nL > 10 || nR > 10) { cerr << "Use tiny graphs only.\n"; return 0; }
11
    vector<vector<int>> adj(nL, vector<int>(nR, 0));
12
    vector<pair<int,int>> edges;
13
    for (int i = 0; i < m; ++i) {
14
        int u, v; cin >> u >> v; --u; --v; adj[u][v] = 1; edges.push_back({u,v});
15
    }
16
    int best = nL + nR + 1;
17
    vector<int> bestL, bestR;
18
    // Enumerate subsets of L and R (2^(nL+nR))
19
    for (int maskL = 0; maskL < (1<<nL); ++maskL) {
20
        for (int maskR = 0; maskR < (1<<nR); ++maskR) {
21
            bool cover = true;
22
            for (auto [u,v] : edges) {
23
                if (((maskL>>u)&1) == 0 && ((maskR>>v)&1) == 0) { cover = false; break; }
24
            }
25
            if (cover) {
26
                int sz = __builtin_popcount((unsigned)maskL) + __builtin_popcount((unsigned)maskR);
27
                if (sz < best) {
28
                    best = sz; bestL.clear(); bestR.clear();
29
                    for (int u = 0; u < nL; ++u) if ((maskL>>u)&1) bestL.push_back(u+1);
30
                    for (int v = 0; v < nR; ++v) if ((maskR>>v)&1) bestR.push_back(v+1);
31
                }
32
            }
33
        }
34
    }
35
    cout << "bruteforce_min_vertex_cover_size = " << best << "\n";
36
    cout << "L:"; for (int u: bestL) cout << ' ' << u; cout << "\n";
37
    cout << "R:"; for (int v: bestR) cout << ' ' << v; cout << "\n";
38
    return 0;
39
}
40