[INFOR] 8 天外奇蹟

題目連結：https://oj.infor.org/problems/8
　　裸的二分匹配圖，每個點的x或y至少要有一個被打到，因此要求最小點涵蓋的大小，又經由koning's theorem可知其大小等於最大匹配的大小，所以就dfs跑一跑或是太閒的話可以用flow寫寫看啦~~

#include<bits/stdc++.h>
using namespace std;
int n,k;
bool rock[509][509];
int my[509];
bool vis[509];
bool dfs(int x)
{
    for(int i = 1; i <= n; i++)
        if(rock[x][i] && !vis[i])
        {
            vis[i] = 1;
            if(!my[i] || dfs(my[i]))
            {
                my[i] = x;
                return true;
            }
        }
    return false;
}
int main()
{
    cin >> n >> k;
    while(k--)
    {
        int a,b; cin >> a >> b;
        rock[a][b] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(!dfs(i)) break;
        else ans++; 
    }
    cout << ans << endl;
}