import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; import java.util.stream.IntStream; public class StronglyConnected { private static int numberOfStronglyConnectedComponents(ArrayList[] adj) { ArrayList[] adjReversa1 = reverseG(adj); boolean[] adjReversalVisited = new boolean[adj.length]; int[] postV = new int[adj.length]; int[] clock = new int[1]; dfs(adjReversa1, adjReversalVisited, postV, clock); // https://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a-sorted-list-of-indices-of-an-array/35701049 int[] temp = IntStream.range(0, postV.length).boxed().sorted((i, j) -> postV[i] - postV[j]).mapToInt(ele -> ele).toArray(); boolean[] visited = new boolean[adj.length]; int sccCount = 0; for (int i = adj.length - 1; i > -1; i--) { if (!visited[temp[i]]) { exploreWithoutPostV(temp[i], adj, visited); sccCount++; } } return sccCount; } private static void dfs(ArrayList[] adj, boolean[] visited, int[] postV, int[] clock) { for (int v = 0; v < adj.length; v++) { if (!visited[v]) explore(v, adj, visited, postV, clock); } } private static void explore(int v, ArrayList[] adj, boolean[] visited, int[] postV, int[] clock) { visited[v] = true; for (int w : adj[v]) { if (!visited[w]) explore(w, adj, visited, postV, clock); } postV[v] = clock[0]; clock[0] = clock[0] + 1; } private static void exploreWithoutPostV(int v, ArrayList[] adj, boolean[] visited) { visited[v] = true; for (int w : adj[v]) { if (!visited[w]) exploreWithoutPostV(w, adj, visited ); } } private static ArrayList[] reverseG(ArrayList[] adj) { ArrayList[] adjReverse = (ArrayList[])new ArrayList[adj.length]; for (int i = 0; i < adj.length; i++) { adjReverse[i] = new ArrayList(); } for (int v = 0; v < adj.length; v++) { for (int w : adj[v]) { adjReverse[w].add(v); } } return adjReverse; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); ArrayList[] adj = (ArrayList[])new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList(); } for (int i = 0; i < m; i++) { int x, y; x = scanner.nextInt(); y = scanner.nextInt(); adj[x - 1].add(y - 1); } System.out.println(numberOfStronglyConnectedComponents(adj)); } }