BOJ. Domino (4196)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringBuilder sb = new StringBuilder();
	static int sccIdx = 1;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int test = toi(br.readLine());
		int[] arr;
		Domino[] dominoes;
		ArrayList<Edge> edges = new ArrayList<>();

		for(int iter = 0; iter < test; iter++) {
			arr = getArr();
			int n = arr[0], m = arr[1];
			dominoes = new Domino[n];
			edges.clear();
			for(int i = 0; i < n; i++) dominoes[i] = new Domino(i);

			for(int i = 0; i < m; i++) {
				arr = getArr();
				int x = arr[0] - 1, y = arr[1] - 1;
				edges.add(new Edge(x, y));
				dominoes[x].list.add(dominoes[y]);
			}

			int[] parent = solve(dominoes);
			HashMap<Integer, Integer> hm = new HashMap<>();
			for(int e: parent)
				if(!hm.containsKey(e)) hm.put(e, 0);

			for(Edge edge: edges) {
				int x = edge.from, y = edge.to;
				if(parent[x] == parent[y]) continue;
				hm.put(parent[y], hm.get(parent[y]) + 1);
			}

			int cnt = 0;
			for(HashMap.Entry<Integer, Integer> entry: hm.entrySet())
				if(entry.getValue() == 0) cnt++;

			sb.append(cnt).append("\n");
		}
		print(sb);
	}

	static class Edge {
		int from, to;
		public Edge(int from, int to) { this.from = from; this.to = to; }
	}

	static int[] solve(Domino[] dominoes) {
		int len = dominoes.length;
		boolean[] finish = new boolean[len];
		int[] parent = new int[len];
		Arrays.fill(parent, -1);
		sccIdx = 1;
		Stack<Integer> stack = new Stack<>();

		for(Domino domino : dominoes) {
			int v = domino.idx;
			if(parent[v] == -1) scc(domino, stack, finish, parent);
		}
		return parent;
	}

	static int scc(Domino domino, Stack<Integer> stack, boolean[] finish, int[] parent) {
		int idx = domino.idx;
		int origVal = parent[idx] = sccIdx++;;
		stack.push(idx);

		for(Domino adj: domino.list) {
			if(parent[adj.idx] == -1) parent[idx] = Math.min(parent[idx], scc(adj, stack, finish, parent));
			else if(finish[adj.idx] == false) parent[idx] = Math.min(parent[idx], parent[adj.idx]);
		}

		if(origVal == parent[idx]) {
			while(true) {
				int popped = stack.pop();
				finish[popped] = true;
				if(popped == idx) break;
			}
		}

		return parent[idx];
	}

	static class Domino {
		int idx;
		ArrayList<Domino> list = new ArrayList<>();
		public Domino(int idx) { this.idx = idx; }
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}