leetcode 547朋友圈

方法一：染色法

类似于岛屿的个数也可以用染色法：通过深度优先搜索来做

使用一个数组来表示当前朋友a是否已经包含到已经遍历的朋友圈中，遍历所有的朋友，如果当前朋友没有在已经访问的朋友圈中，即visited==false，那么cnt++;并将该朋友所有相关的朋友使用dfs全部标记为visited=true;

当遍历完成时，cnt即为结果；并且不改变原数组，时间复杂度O(n^2)，即遍历M的每个元素；空间复杂度为O(n);

C++代码：

class Solution {

public:

    int findCircleNum(vector<vector<int>>& M) {

        int m=M.size();

        if(m==) return ;

        int cnt=;

        vector<bool>visited(m,false);

        for(int i=;i<m;i++){

            if(!visited[i]){

                dfs(M,visited,i);

                cnt++;

            }

        }

        return cnt;

    }

    void dfs(vector<vector<int>>&M,vector<bool>&visited,int i){

        int m=M.size();

        for(int j=;j<m;j++){

            if(M[i][j]== && !visited[j]){

                visited[j]=true;

                dfs(M,visited,j);

            }

        }

    }

};

方法二：并查集

//使用并查集，基本思想是假设所有人都独立，初始化朋友圈为n个，如果两个人相关那么n--，将所有人遍历可得到朋友圈个数；

class Solution {

public:

    int findCircleNum(vector<vector<int>>& M) {

        int n=M.size();

        if(n==) return ;

        int groups=n;

        vector<int>leads(n,);

        for(int i=;i<n;i++) leads[i]=i;

        for(int i=;i<n;i++){

            for(int j=i+;j<n;j++){

                if(M[i][j]==){

                int lead1=find(i,leads);

                int lead2=find(j,leads);

                if(lead1!=lead2){

                    groups--;leads[lead1]=lead2;

                }

                }

            }

        }

        return groups;

    }

private:

    int find(int x,vector<int>&parents){

        if(x==parents[x])

            return x;

        else

            return find(parents[x],parents);

    }

};

巴特西

leetcode 547朋友圈

最新文章

热门文章