Good day.

I can not figure out how the correct algorithm should look like (C # language, but it does not matter).

There are N elements z1, z2, ..., zN. The two elements zi and zj may have a connectedness (or they may not). Connectedness is transitive. Those. if zi and zj are connected, and also zj and zk are connected, then zi and zk are also connected.

Relationships can be expressed by a matrix, where 1 denotes connectedness, 0 - its absence. Having a similar matrix, it is necessary to count the number of clusters, i.e. subsets of elements; in each cluster, all elements are related to each other, but not related to elements from other clusters.

Example 1: 4 elements

1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1

From here, it is possible to see that elements 1 and 2 are connected, also 2 and 3 => are connected 1,2, and 3, forming the 1st cluster. Element 4 is not associated with anyone, and forms the 2nd cluster of one element.

Example 2: 3 elements

 1 0 0 0 1 0 0 0 1

here, as you can see, there are three clusters of one element each.

2 answers 2

Well, this is a normal undirected graph, an indentation matrix, a search for connected components ... Just perform a search in depth (or width).

Descriptions are everywhere, see, for example, here .

I can implement only in C ++, C # can only read, but not write :)

  • I can read in C ++, I can not write) - user211576

I wrote this JavaScript implementation:

 var arr = [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]]; //var arr = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]; //var arr = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]; var check = function(i) { var was1 = false; for (var j=0; j<arr.length;j++) { if (arr[i][j] == 1) { was1 = true; arr[i][j] = 0; check(j); } } if (was1) return 1; else return 0; } var count = 0; for (var i=0; i<arr.length;i++) { count += check(i); } alert(count);