eolymp
bolt
Try our new interface for solving problems
Problems

Strong connectivity

Strong connectivity

A \textbf{strongly connected component} in a directed graph is an arbitrary set of vertices such that from any vertex of this set there is a path to any other vertex of this set, and there is no other set with a similar property containing this set. Given a directed graph. Find the number of strongly connected components in it. \InputFile The first line contains two integers $n$ and $m~(1 \le n \le 10, 0 \le m \le 90)$ --- number of vertices and edges in the graph, respectively. The next $m$ lines describe the edges: $i$-th of these lines contains two integers $u_i$ and $v_i~(1 \le u_i, v_i \le n)$ --- the start and the end of the $i$-th edge respectively. It is guaranteed that the graph has no loops or multiple edges. \OutputFile Print the number of strongly connected components in the graph. \includegraphics{https://static.e-olymp.com/content/6d/6d35215b8602960135be10b0b5af1e116fcc5452.gif}
Time limit 1 second
Memory limit 128 MiB
Input example #1
3 2
1 2
2 3
Output example #1
3
Input example #2
5 4
3 1
1 2
2 3
4 5
Output example #2
3
Source SСS - 2011 Sevastopol 08/08/2011 d.2 1st League