- 2 Connected Groups Relationships Between People May Be Represented In A Matrix As A Series Of Binary Digits For Exampl 1 (86.97 KiB) Viewed 26 times
Thank you
2. Connected Groups Relationships between people may be represented in a matrix as a series of binary digits. For example, the direct relationships for person with persons 0 through 5 might be shown as 101100. This means that person Oknows persons 0, 2 and 3, the indices of each of the 1 values. A relationship is transitive. In other words, if person Oknows person 2 and person 2 knows person 3, then person knows person 3 through person 2. A group is composed of all of the people who know one another, whether directly or transitively. Example Consider the following relationships matrix: 0 1 012 1 1 1 0 1 0 200 1 Persons 0 and 1 are connected, while person 2 is not. There are 2 groups. Determine the number of groups represented in a matrix. Note: The method signatures may vary slightly depending on the requirements of the chosen language. For example, C language will have an argument that represents the number of rows and columns in the matrix. Also, Java will receive a list rather than an array.
Function Description Complete the function countGroups in the editor below. countGroups has the following parameter(s): string related[n]: an array of strings of binary digits related that represent connections of people Returns: int: an integer that represents the number of groups of people Constraints • 1≤n≤300 • 0≤i<n • [related] =n • Each related contains a binary string of n zeros and ones. related is a square matrix. ▸ Input Format for Custom Testing ▾ Sample Case 0 Sample Input STDIN 4 1100 1110 0110 0001 Function 2 → size of related [] n = 4 related = ['1100', '1110', '0110', '0001'] Sample Output
Explanation Squares highlighting a connection between two people are highlighted in green. Each of the people is known to self, so they are highlighted in gray. 0 1 2 3 related[] 2 0 1 1 1 1 1 3 00 1 0 01 1 00 0 1 yu 0 The 2 groups formed are: {related[0], related[1], related[2]} and {related[3]} There are n = 4 people numbered related[0] through related[3]. There are 2 pairs who directly know each another: (related[0], related[1]) and (related[1], related[2]). Because a relation is transitive, the set of people {related[0], related[1], related[2]} is considered a single group. The remaining person, related[3], does not know any other people and is a separate group: {related[3]}. There are a total of 2 groups.
Sample Input STDIN 5 size of related [] n = 5 10000 → related= ['10000', '01000', '00100', '00010', '00001'] 01000 00100 00010 00001 Sample Output 5 Explanation 0 Function 10000 0 00 related [] 1 000 0100 001 0 0 0 0 1 No direct relationships are shown so there are 5 groups: {related[0]}, {related[1]}, {related[2]}, {related[3]}, and {related[4]}.