二分图.cpp

来自「图论的一些常用代码」· C++ 代码 · 共 52 行

#include<iostream>
#include<string>
using namespace std;
bool g[201][201];
int n, m, ans;
bool b[201];
int relating[201];

bool init ()
{
    int _x, _y;
    ans = 0;
    if (cin >> n >> m)return false;
    for (int i = 1; i <= n; i ++)
    {
        cin >> _x;
        for (int j = 0; j < _x; j ++)
        {
            cin >> _y;
            g[i][_y] = true;
        }
    }
    return true;
}

bool find (int a)
{
    for (int i = 1; i <= m; i ++)
    {
        if (g[a][i] == 1 && ! b[i])
        {
            b[ i ] = true;
            if (relating[i] == 0 || find(relating[i]))
            {
                relating[i] = a;
                return true;
            }
        }
    }
    return false;
}

int main ()
{
    while (init())
    {
        for (int i = 1; i <= n; i ++)
            if (find(i))ans ++;
        cout << ans;
    }
}