250424 단방향 링크 네트워크

private static class Matcher {
	private final int n;
	private final List<List<Integer>> graph;
	private final int[] matched;
	private boolean[] visited;

	Matcher(int n) {
		this.n = n;
		this.graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}
		this.matched = new int[n];
		Arrays.fill(matched, -1);
	}

	void addEdge(int from, int to) {
		graph.get(from).add(to);
	}

	int maxMatching() {
		int matches = 0;
		for (int i = 0; i < n; i++) {
			visited = new boolean[n];
			if (dfs(i)) {
				matches++;
			}
		}
		return matches;
	}

	private boolean dfs(int node) {
		for (int neighbor : graph.get(node)) {
			if (visited[neighbor]) {
				continue;
			}
			visited[neighbor] = true;
			if (matched[neighbor] == -1 || dfs(matched[neighbor])) {
				matched[neighbor] = node;
				return true;
			}
		}
		return false;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringBuilder sb = new StringBuilder();

	int testCases = Integer.parseInt(br.readLine());

	for (int t = 0; t < testCases; t++) {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		Matcher matcher = new Matcher(n);

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			matcher.addEdge(u, v);
		}

		sb.append(matcher.maxMatching()).append("\n");
	}

	bw.write(sb.toString());
	bw.flush();
	bw.close();
}

출처:https://www.acmicpc.net/problem/3295