386. Friend Circles
The graph arrives as a MATRIX this time, not an edge list. Row i column j
holds 1 when person i and person j are friends and 0 when they are not.
Everyone is listed as their own friend, so the diagonal is all 1.
Friendship is passed along: if A knows B and B knows C, all three sit in one circle even if A and C have never met. Print how many circles there are.
This is problem 363 with the input in a different shape. There is no adjacency
list to build; the neighbours of i are the columns holding 1 in row i,
which turns finding them into a scan of the row.
That scan is the cost of a matrix, and it is worth feeling. Every traversal step
looks at all n columns whether they hold edges or not, so the work is n²
even when almost nobody is friends. An adjacency list would have been n + m.
People are numbered 1 to n in the statement, but the matrix is indexed from 0
in every language, so pick one convention and hold it.
Constraints - `1 ≤ n ≤ 1000` - Every value is `0` or `1`. - The matrix is symmetric and the diagonal is all `1`.
Input
The first line contains a single integer n, the number of people. Each of the
next n lines contains n integers separated by spaces, each 0 or 1. The
matrix is symmetric and its diagonal is all 1.
Output
Print one integer, the number of friend circles.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.