How many separate groups of friends

n people are given as an n by n grid. grid[i][j] is 1 when person i and person j are directly connected, and 0 when they are not. Being connected is mutual, and everybody is connected to themselves.

A group is a set of people who can all reach each other, directly or through others. Count the groups.

Worked example#

110
110
001

Person 0 and person 1 are connected. Person 2 is connected to nobody but themselves. So there are 2 groups.

Now this one:

110
111
011

0 knows 1, and 1 knows 2. So 0 and 2 are in the same group even though they do not know each other directly, and the answer is 1.

The idea#

This is a graph wearing a grid. The people are nodes, the 1s are edges, and "how many groups" is "how many connected components".

Counting components is the same walk every time:

seen = nothing
for each node:
    if it has not been seen:
        count += 1
        walk everything reachable from it, marking as seen

The walk itself can be depth first or breadth first: it makes no difference here, because you are not asking how far anything is, only what is reachable. Take whichever you find easier to write.

The one thing that matters#

Mark a node as seen when you put it on the stack, not when you take it off. Otherwise a node reachable two ways gets added twice, and on a dense graph that grows fast enough to matter.

That check is the only difference between walking a graph and walking a tree. A tree has exactly one route to each node, so nothing has to be remembered. A graph can have many, and the "have I been here" set is what stops you going round for ever.

Constraints#

• 1 <= n <= 200
• grid[i][i] is always 1, and grid[i][j] equals grid[j][i]