If the input matrix is guaranteed to describe transitive connectivity, it has a peculiar form that allows for an algorithm probing only a subset of the matrix elements. Here is an example implementation in Python:
def count_connected_groups(adj):
n = len(adj)
nodes_to_check = set([i for i in range(n)]) # [] not needed in python 3
count = 0
while nodes_to_check:
count += 1
node = nodes_to_check.pop()
adjacent = adj[node]
other_group_members = set()
for i in nodes_to_check:
if adjacent[i]:
other_group_members.add(i)
nodes_to_check -= other_group_members
return count
# your example:
adj_0 = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# same with tuples and booleans:
adj_1 = ((True, True, False), (True, True, False), (False, False, True))
# another connectivity matrix:
adj_2 = ((1, 1, 1, 0, 0),
(1, 1, 1, 0, 0),
(1, 1, 1, 0, 0),
(0, 0, 0, 1, 1),
(0, 0, 0, 1, 1))
# and yet another:
adj_3 = ((1, 0, 1, 0, 0),
(0, 1, 0, 1, 0),
(1, 0, 1, 0, 0),
(0, 1, 0, 1, 0),
(0, 0, 0, 0, 1))
for a in adj_0, adj_1, adj_2, adj_3:
print(a)
print(count_connected_groups(a))
# [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# 2
# ((True, True, False), (True, True, False), (False, False, True))
# 2
# ((1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (0, 0, 0, 1, 1), (0, 0, 0, 1, 1))
# 2
# ((1, 0, 1, 0, 0), (0, 1, 0, 1, 0), (1, 0, 1, 0, 0), (0, 1, 0, 1, 0), (0, 0, 0, 0, 1))
# 3
An optimized version of the same algorithm (less readable, but faster and more easily translatable into other languages) is the following: