Strongly Connected Components - Classic Problems | Repovive

CLS42. Strongly Connected Components

2s256 MB

Given a directed graph with $n$ vertices and $m$ edges, find the number of strongly connected components (SCCs).

A strongly connected component is a maximal set of vertices such that there is a path from every vertex to every other vertex within the set.

Constraints

$1 \le n \le 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le u, v \le n$ for each edge
No self-loops
There may be multiple edges between the same pair of vertices

Input

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Output

components

Samples

Input

Explanation

Vertices 1, 2, and 3 form one SCC because they lie on the cycle 1 -> 2 -> 3 -> 1. Vertices 4 and 5 form another SCC because 4 reaches 5 and 5 reaches 4.

Output

Input

Explanation

All edges go from a smaller-numbered vertex to a larger-numbered vertex. No two different vertices can reach each other both ways, so each vertex is its own SCC.

Output

Input

Explanation

The edges form the cycle 1 -> 2 -> 3 -> 4 -> 1. Every vertex can reach every other vertex, so all four vertices are in one SCC.

Output

Given a directed graph with $n$ vertices and $m$ edges, find the number of strongly connected components (SCCs).

A strongly connected component is a maximal set of vertices such that there is a path from every vertex to every other vertex within the set.

$1 \le n \le 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le u, v \le n$ for each edge
No self-loops
There may be multiple edges between the same pair of vertices

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

components