AcWing 1394. 完美牛棚 (java)
原题链接
中等
作者:
x_x_5
,
2024-04-19 14:46:06
,
所有人可见
,
阅读 1
import java.util.*;
class Main {
static Set<Integer>[] favor;
static int[] match;
static boolean[] vt;
public static boolean find(int i) {
if (vt[i]) return false;
vt[i] = true;
for (int r : favor[i]) {
if (match[r] == 0 || find(match[r])) {
match[r] = i;
return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
favor = new HashSet[n + 1];
for (int i = 1; i <= n; ++ i) {
favor[i] = new HashSet<>();
for (int c = sc.nextInt(); c > 0; -- c) {
favor[i].add(sc.nextInt());
}
}
int cnt = 0;
match = new int[m + 1];
for (int i = 1; i <= n; ++ i) {
vt = new boolean[n + 1];
if (find(i)) cnt ++;
}
System.out.println(cnt);
}
}