【 Strange skill and crafty 】– Moments of friends (and check collection)

Circle of friends

There are N students in the class. Some of them are friends, some of them are not. Their friendship is transmissive. If we know that A is A friend of B and B is A friend of C, then we can assume that A is also A friend of C. The so-called circle of friends refers to the collection of all friends.

Given an N * N matrix M, represents the friendship relationship between students in the class. If M[I][j] = 1, it means that the ith and j students are known to be friends of each other; otherwise, it is not known. You must output the total number of known friends among all students.

Example 1:

Input:

[[1.1.0],
 [1.1.0],
 [0.0.1]]
Copy the code

Student 0 and student 1 are friends of each other. They are in the same circle of friends. The second student is in a circle of friends. So return 2.

Example 2:

Input:

[[1.1.0],
 [1.1.1],
 [0.1.1]]
Copy the code

Note: Student 0 and student 1 are friends of each other, student 1 and student 2 are friends of each other, so student 0 and student 2 are friends of each other, so the three of them are in the same circle of friends, return 1.

Note:

N within the range of [1,200]. For all students, M[I][I] = 1. If M[I][j] = 1, then M[j][I] = 1.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/fr… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Train of thought

Code implementation

int findCircleNum(vector<vector<int>>& M) {
        int n=M.size(a);int count=n;
        // Initialization process
        vector<int> root(n,0);/ / n
        for(int i=0; i<n; i++) { root[i]=i;// The root node of each node is set to itself
        }
        for(int i=0; i<n- 1; i++)for(int j=i+1; j<n; j++)// This traversal is not repeated
            {
                if(M[i][j])// The two are friends
                {
                    int p=getRoot(root,i);
                    int q=getRoot(root,j);
                    if(p! =q){ root[p]=q; count--; }}}return count;
    }
    
    int getRoot(vector<int>&root,int k){
        while(root[k]! =k){ k=root[k]; }return k;
    }
Copy the code

Of course, the time complexity of deep and wide searches will be low.