Leetcode --- 및 검색 집합

간단 한 소개
             그리고 집합 을 찾 는 것 은 일종 의 데이터 구조 이다. 일반적으로 그림 (사실은 무방 향 그림 을 해결 하 는 것) 의 연결 분량 문 제 를 처리 하지만 집합의 루트 노드 가 더 많은 정 보 를 유지 할 수 있 을 때 집합 을 찾 으 면 범위 가 더욱 넓 은 무방 향 그림 을 바탕 으로 하 는 연결 분량 문 제 를 해결 할 수 있다.이렇게 많은 문 제 를 풀 고 집 을 찾 은 후에 저 는 사물 과 사물 간 의 관계 문 제 를 해결 하 는 데이터 구조 라 고 생각 합 니 다. 그리고 이런 관 계 는 전달 가능 한 관계 여야 하기 때문에 이런 문 제 를 만나면 먼저 사용 하고 집 을 찾 아 해결 할 수 있 습 니 다.
그리고 집합 을 찾 는 작업 이 비교적 간단 하 다. 주로 경로 의 압축 을 이해 하고 값 에 따라 병합 하 며 권한 을 가지 고 집합 을 찾 으 면 ok 이다.
 
제목.
         547. 친구 권 (무방 향 그림 연결 분량 구하 기)
684. 중복 연결 (방향 도, 연결 분량 없 음)
685. 중복 연결 II (이전 문제 의 개편)
839. 유사 문자열 그룹 (그림, 연결 분량 없 음)
면접 문제 17.07. 아기 이름 (순위 에 따라 병합)
200. 섬 수 (DFS 고전 웅덩이 문제 해결)
 
547. 친구 권 (무방 향 그림 연결 분량 구하 기)

class Solution {
public:

    //     
    int fa[11111];
    int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}
    bool Union(int x,int y)
    {
        int rx = Find(x), ry = Find(y);
        if(rx == ry)return false;
        fa[rx] = ry;
        return true;
    }

    int findCircleNum(vector>& M) {
        memset(fa,-1,sizeof fa);

        int n = M.size();    
        if(!n) return 0;
        int m = M[0].size();

        for(int i = 0;i>& M) {
        int n = M.size();
        if(!n) return 0;
        int m = M[0].size();
        
        vector vis(n+1,false);
        int ans = 0;

        for(int i = 0;i>&M,vector&vis,int i)
    {
        if(vis[i]) return;
        vis[i] = true;
        
        for(int j = 0;j

 
 
684. 중복 연결 (방향 도, 연결 분량 없 음)

class Solution
{
    public:
    
    int fa[11111];
    int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}
    bool Union(int x,int y)
    {
        int rx = Find(x), ry = Find(y);
        if(rx == ry)return false;
        fa[rx] = ry;
        return true;
    }

    vector findRedundantConnection(vector>& edges) {
        memset(fa,-1,sizeof fa);
        int n = edges.size();

        for(int i = 0;i{};
    }
};

 
685. 중복 연결 II (이전 문제 의 개편)

class Solution {
public:
    

    int fa[11111];
    int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}
    bool Union(int x,int y)
    {
        int rx = Find(x), ry = Find(y);
        if(rx == ry)return false;
        fa[rx] = ry;
        return true;
    }

    vector check(vector>& edges,int except)
    {
        memset(fa,-1,sizeof fa);
        for(int i = 0;i findRedundantDirectedConnection(vector>& edges) {
        
        int n = edges.size();    
        std::vector degree(n+11,0);
        for(auto &x:edges) ++degree[x[1]];

        for(int i = n-1;i>=0;--i)
        {
            if(degree[edges[i][1]] == 2 && !check(edges,i).size())
            {//       2  ，           ，    ，      
                return edges[i];
            }
        }
        return check(edges,n);

    }
};

 
 
 
839. 유사 문자열 그룹 (그림, 연결 분량 없 음)

class Solution {
public:
    bool isSame(string &a,string &b)
    {
        int n = a.size(),m=b.size();
        if(n != m) return false;
        int cnt = 0;
        for(int i = 0;ifa;

    int Find(int x)
    {
        return x == fa[x]? x: fa[x] = Find(fa[x]);
    }
    
    void Union(int x,int y)
    {
        int fx=Find(x),fy = Find(y);
        if(fx == fy)return;
        fa[fx] = fy;
    }

    int numSimilarGroups(vector& A) {
        int n = A.size();
        fa.resize(n);
        for(int i = 0;i

 
면접 문제 17.07. 아기 이름 (순위 에 따라 병합)

class Solution {
public:

    unordered_map fa;//     
    unordered_map mp;//     :    
  //  unordered_map mp;

    string Find(string x)
    {
        return fa[x] == x?x:fa[x] = Find(fa[x]);
    }

    void Union(string x,string y)
    {
        string fax = Find(x);
        string fay = Find(y);
        if(fax == fay)return;
        if(fax trulyMostPopular(vector& names, vector& synonyms) {
       
        for(auto x:names)
        {//   
            int pos = x.find("(");
            string name = x.substr(0,pos);
           int pos2 = x.find(")");
            string fre = x.substr(pos+1,pos2-pos+1);
            mp[name] = stoi(fre);
            fa[name] = name;

        }
        for(auto x:synonyms)
        {//   
            int pos = x.find(",");
            int pos2 = x.find(")");
            int sz = x.size();
            string name1 = x.substr(1,pos-1);
            string name2 = x.substr(pos+1,sz-1-pos-1);
            fa[name1] = name1;
            fa[name2] = name2;
        }

        for(auto x:synonyms)
        {//  
            int pos = x.find(",");
            int pos2 = x.find(")");
            int sz = x.size();
            string name1 = x.substr(1,pos-1);
            string name2 = x.substr(pos+1,sz-1-pos-1);
            // fa[name1] = name1;
            // fa[name2] = name2;
            Union(name1,name2);
        }

        vectorans;
        for(auto x:fa)
        {
            if(x.first == x.second)
            {
                string s = x.first + "(" + to_string(mp[x.first]) + ")" ;
                ans.push_back(s);
            }
        }
        return ans;


    }

};

 
 
 
200. 섬 수 (DFS 고전 웅덩이 문제 해결)

class Solution {
public:

    //     
    int fa[111111];
    int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}
    bool Union(int x,int y)
    {
        int rx = Find(x), ry = Find(y);
        if(rx == ry)return false;
        fa[rx] = ry;
        return true;
    }
     int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    int numIslands(vector>& grid) {
        int n = grid.size();
        if(!n)return 0;

        int m = grid[0].size();
        memset(fa,-1,sizeof fa);

        for(int i = 0;i=n||dy<0||dy>=m)continue;
                        if(grid[dx][dy] == '1')Union(i*m+j,dx*m+dy);
                    }
                }
            }
        int ans = 0;
        for(int i = 0;i>& M) {
         int n = M.size();
        if(!n) return 0;
        int m = M[0].size();
        
        int ans = 0;
        for(int i = 0;i>&M,int i,int j,int n,int m)
    {
        if(i>=n || i<0 || j>=m || j<0)return;
        if(M[i][j] != '1')return;
        
        M[i][j] = '0';
        dfs(M,i+1,j,n,m);
        dfs(M,i-1,j,n,m);
        dfs(M,i,j-1,n,m);
        dfs(M,i,j+1,n,m);
    }
};