思路

我们可以使用二分图匹配来做这个题目。我们把每一个小行星的横坐标和纵坐标映射到二分图上，找最大匹配即可。

代码

// POJ3041.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 510;
int n, k, head[MAX_N], current, tmpx, tmpy, dfn[MAX_N], match[MAX_N], ans;
struct edge
{
    int to, nxt;
} edges[21000];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
bool dfs(int u, int tm)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (dfn[to] != tm)
        {
            dfn[to] = tm;
            if ((!match[to]) || dfs(match[to], tm))
            {
                match[to] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy);
    for (int i = 1; i <= n; i++)
        if (dfs(i, i))
            ans++;
    printf("%d", ans);
    return 0;
}