POJ 3041
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
int adj[505], nxt[10005], to[10005], ecnt, mate[505], vis[505], idx, n, m;
inline void addEdge(int f, int t)
{
nxt[++ecnt] = adj[f], adj[f] = ecnt, to[ecnt] = t;
}
bool hungry(int u)
{
for (int e = adj[u]; e; e = nxt[e])
if (!mate[to[e]])
return mate[to[e]] = u, true;
for (int e = adj[u]; e; e = nxt[e])
if (vis[to[e]] != idx)
{
vis[to[e]] = idx;
if (hungry(mate[to[e]])) return mate[to[e]] = u, true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, x, y; i < m; i++)
scanf("%d%d", &x, &y), addEdge(x, y);
int ans = 0;
for (int i = 1; i <= n; i++)
{
idx++;
if (hungry(i)) ans++;
}
printf("%d", ans);
return 0;
}