import java.util.*; /** * * @author blog.csdn.net/ljfbest * * poj 1274(二分匹配) * 题意: n牛,m个房子,每个牛都只住在自己想住的房子里面,一个房子只能住一个牛,问最多可以安排多少头牛入住 */ public class Main { Scanner sc = new Scanner(System.in); int N,M,temp,count; boolean[][] map; int[] stall; boolean[] visit; boolean find(int index){ for(int i=1;i<=M;i++){ if(map[index][i]&&!visit[i]){ visit[i]=true; if(stall[i]==0||find(stall[i])){ stall[i]=index; return true; } } } return false; } void init(){ while(sc.hasNext()){ count=0; N=sc.nextInt(); M=sc.nextInt(); map=new boolean[N+1][M+1]; stall=new int[M+1]; for(int i=1;i<=N;i++){ temp=sc.nextInt(); while(temp--!=0) map[i][sc.nextInt()]=true; } for(int i=1;i<=N;i++){ visit=new boolean[M+1]; if(find(i)) count++; } System.out.println(count); } } public static void main(String[] args) throws Exception { new Main().init(); } }