BOJ - 11375 ) 열혈강호

 

---

www.acmicpc.net/problem/11375

11375번: 열혈강호

 

---

직원그룹과 해야할일그룹 두 그룹간에 매칭을 시켜주는 전형적인 이분매칭 문제이다.

 

1 ) 현재를 이을것인지?

 

2 ) 이어진 현재를 바꿔서 나를 이을것인지? 의 두가지를 구현하면되는데,

 

재귀함수로 구현할 수 있다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 열혈강호 {

	private static int c[],n,m;
	private static boolean visit[];
	private static ArrayList<Integer> node[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		node = new ArrayList[n+1];
		for(int i =1;i<=n;i++)node[i] = new ArrayList<>();
		for(int i = 0 ; i < n ; i ++) {
			st = new StringTokenizer(br.readLine()); 
			int t = Integer.parseInt(st.nextToken());
			while(t-->0) {
				int s = i+1;
				int e = Integer.parseInt(st.nextToken());
				node[s].add(e);
			}
		}
		int answer=0;
		c= new int[m+1];
		for(int i = 1 ; i <=n ; i++) {
			visit = new boolean[m+1];
			if(dfs(i)) {
				answer++;
			}
			
		}System.out.println(answer);
	}

	private static boolean dfs(int x) {
		for(int i = 0 ; i < node[x].size() ; i++) {
			int now = node[x].get(i);
			if(!visit[now]) {
				visit[now] = true;
				if(c[now]==0 || dfs(c[now])) {
					c[now]=x;
					return true;
				}
			}
		}
		return false;
	}

}

---