Graph traversal. Connectivity component
Problem
An undirected unweighted graph is given. For it, you need to find the number of vertices that lie in the same connected component with a given vertex (counting this vertex).
Input: The first line of the input contains two numbers: N and S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), where N– the number of graph vertices, and S – given top. The next N lines contain N numbers each – graph adjacency matrix, where 0 means no edge between vertices, and 1 – its presence. It is guaranteed that there are always zeros on the main diagonal of the matrix.
Output: Print a single integer – desired number of vertices.
Examples
| # |
Input |
Output |
| 1 |
3 1
0 1 1
1 0 0
1 0 0
| 3 |