Алгоритм Куна
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 251;
 
vector<int> G2B(MAX, 0);
vector< vector<int> > G(MAX);
vector<int> C(MAX, 0);
int k;
 
int dfs(int b)
{
    if (C[b] != k)
    {
        C[b] = k;
        for (int i = 0; i < G[b].size(); i++)
        {
            if (G2B[G[b][i]] == 0 || dfs(G2B[G[b][i]]))
            {
                G2B[G[b][i]] = b;
                return 1;
            }
        }
    }
    return 0;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        while(true)
        {
            int a = -1;
            cin >> a;
            if (a == 0) break;
            G[a].push_back(i);
        }
    }
 
    int res;
    for (k = 1, res = 0; k <= m; k++)
        res += dfs(k);
 
    cout << res << endl;
    for (int i = 1; i <= n; i++)
    {
        if (G2B[i] != 0)
            cout << i << " " << G2B[i] << endl;
    } 
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License