leetcode 547. 朋友圈 dfs | 并查集

╰+哭是因爲堅強的太久メ 2022-12-12 04:53 141阅读 0赞

**dfs**  
**每次拿到一个没有访问的节点  
就dfs一遍把它和它的朋友都标记了  
最后看看dfs了几次就有几个朋友圈**

class Solution { 
    public:
        vector<bool>visit;
        int findCircleNum(vector<vector<int>>& M) { 
            if(M.size()==0){ 
                return 0;
            }
            visit = vector<bool>(M.size(),false);
            int ret = 0;
            for(int i=0;i<M.size();i++){ 
                if(!visit[i]){ 
                    dfs(i,M);
                    ret++;
                }
            }
            return ret;
        }
        
        bool dfs(int i,vector<vector<int>>& M){ 
            visit[i] = true;
            for(int j=0;j<M[i].size();j++){ 
                if(M[i][j]==1 && visit[j] == false){ 
                    dfs(j,M);
                }
            }
            return true;
        }
    };

![在这里插入图片描述][20201006135156460.png_pic_center]

--------------------

**并查集**

class US{ 
        public:
        vector<int> parent;
        
        US(int n){ 
            
            parent = vector<int> (n,0);
            for(int i=0;i<n;i++){ 
                parent[i] = i;
            }
        }
            
        int findP(int n){ 
            
            while( parent[n] !=n ){ 
                n = parent[n];
            }
            return n;
        }
        
        bool unionxy(int x,int y){ 
            
            int yp = findP(y);
            int xp = findP(x);
            parent[yp] = xp;
            return true;
        }
    };
    
    class Solution { 
    public:
        vector<bool>visit;
        int findCircleNum(vector<vector<int>>& M) { 
            US u(M.size());
            for(int i=0;i<M.size();i++){ 
                for(int j=0;j<M[i].size();j++){ 
                    if(M[i][j]==1){ 
                        u.unionxy(i,j);
                    }
                }
            }
            int ret = 0;
            for(int i=0;i<M.size();i++){ 
                if(u.parent[i] == i){ 
                    ret++;
                }
            }
            return ret;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70_pic_center]

[20201006135156460.png_pic_center]: /images/20221123/edbf54a9531e48a3bc38f38623155fef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/04b251aa2d6d434eb14e8a71ae0f70f7.png