题目链接:POJ 1469 COURSES
题目大意:
题解:
二分图匹配模板。
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
int t, p, n, link[310], ans, cnt, head[310];
bool vis[310];
struct Edge {
int v, next;
} edge[30010];
void addEdge(int u, int v) {
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
bool hungry(int u) {
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (!vis[v]) {
vis[v] = true;
if (!link[v] || hungry(link[v])) {
link[v] = u;
return true;
}
}
}
return false;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &p, &n);
cnt = 0;
memset(head, 0, sizeof(head));
memset(link, 0, sizeof(link));
for (int i = 1, k, x; i <= p; ++i) {
scanf("%d", &k);
while (k--) {
scanf("%d", &x);
addEdge(i, x);
}
}
ans = 0;
for (int i = 1; i <= p; ++i) {
memset(vis, 0, sizeof(vis));
ans += hungry(i);
}
if (ans == p) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}