CSES - School Dance | Vũ hội trường

Authors:

Flower_On_Stone , nhphucqt , NguyễnAnhQuốc_83

Problem types

Points: 2000 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

There are n boys and m girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are k potential pairs.

Your task is to find out the maximum number of dance pairs and show how this number can be achieved.

Input

The first input line has three integers \(n\), \(m\) and \(k\): the number of boys, girls, and potential pairs. The boys are numbered \(1, 2, \ldots, n\), and the girls are numbered \(1, 2, \ldots, m\).
After this, there are \(k\) lines describing the potential pairs. Each line has two integers \(a\) and \(b\): boy \(a\) and girl \(b\) are willing to dance together.

Output

First print one integer \(r\): the maximum number of dance pairs. After this, print \(r\) lines describing the pairs. You can print any valid solution.

Constraints

\(1 \leq n, m \leq 500\)
\(1 \leq k \leq 1000\)
\(1 \leq a \le n\)
\(1 \leq b \le m\)

Example

Sample input

Sample output

2
1 2
3 1

Comments

include <bits/stdc++.h>

using namespace std;

const int MAXN = 500;
vector<int> adj[MAXN];
int match[MAXN];
bool visited[MAXN];

bool dfs(int u) {
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m, k;
cin >> n >> m >> k;


for (int i = 0; i < n; ++i) {
    adj[i].clear();
}
fill(match, match + m, -1);


for (int i = 0; i < k; ++i) {
    int a, b;
    cin >> a >> b;
    adj[a - 1].push_back(b - 1);
}


int max_matching = 0;
for (int u = 0; u < n; ++u) {
    fill(visited, visited + m, false);
    if (dfs(u)) {
        ++max_matching;
    }
}

cout << max_matching << "\n";
vector<pair<int, int>> result;
for (int v = 0; v < m; ++v) {
    if (match[v] != -1) {
        result.emplace_back(match[v] + 1, v + 1);
    }
}

for (const auto &p : result) {
    cout << p.first << " " << p.second << "\n";
}

return 0;

}
Code tham khảo