C++, standard union find solution,


  • 0

    Just a standard union find solution, could be used in other question .

     int findCircleNum(vector<vector<int>>& M) {
            int m = M.size();
            vector<int> student(m, 0);
            for(int i = 0;i < m;i++)
                student[i] = i;
            int count = m;
            for(int i = 0;i < m;i++)
            {
                for(int j = i + 1;j < m;j++)
                {
                    if(M[i][j] == 1)
                    {
                        int left = i;
                        int right = j;
                        while(student[left] != left)
                            left = student[left];
                        while(student[right] != right)
                            right = student[right];
                        if(left != right)
                        {
                            count--;
                            student[left] = right;
                        }
                    }
                }
            }
            return count;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.