eolymp
bolt
Try our new interface for solving problems
Problems

Connected components

Connected components

The undirected unweighted graph is given. Find the number of its connected components. \InputFile The first line contains the number of vertices $n\:(n \le 100)$ in the graph. Then, in $n$ lines, an $n$ by $n$ matrix is given --- the adjacency matrix of the graph. In the $i$-th row, at the $j$-th position, there is a $1$ if vertices $i$ and $j$ are connected by an edge, and $0$ if there is no edge between them. The main diagonal of the matrix contains zeroes. The matrix is symmetric with respect to the main diagonal. \OutputFile Print the number of connected components in a graph. \includegraphics{https://static.e-olymp.com/content/55/557b6326cb14d307dd67dfa6f952574cb6f8e559.gif}
Time limit 1 second
Memory limit 128 MiB
Input example #1
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
Output example #1
3
Source 2011 Summer school, Sevastopol, August 8, Day 1, League 1