Condensation of the graph

Condensation of the graph

Find the number of edges in the condensation of a given directed graph.

The condensation of a directed graph G is a directed graph G', whose vertices are strongly connected components of G, and the edge in G' is present only if there exists at least one edge between the vertices of corresponding connected components.

The graph condensation does not contain multiple edges.


The first line contains two positive integers n and m (n10000, m100000) - the number of vertices and edges in a graph correspondingly. Each of the next m lines describes the edge of the graph. The edge number i is given with two positive integers bi, ei (1bi, ein) - the beginning and finishing vertex of the graph. The input graph may contain the multiple edges and loops.


The number of edges in graph condensation.

Time limit 1 seconds
Memory limit 256 MiB
Input example #1
4 4
2 1
3 2
2 3
4 3
Output example #1
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9