[Union-Find] Union-Find | C++

Union-FInd

• 그래프 알고리즘 중 하나로 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하하는지 판별하는 알고리즘.
• disjoint set들을 관리하기 위한 data structure
  • makeset(x) : 단일 element x로 이루어진 set을 하나 생성한다.
  • find(x) : x가 포함된 set을 return한다.
  • union(x,y) : x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다.
• union-find는 각 set을 rooted tree로 관리하고, 각 tree의 root를 대표 element로 지정한다. 
• 각 대표 element는 rank를 가지고 있다.
• rank는 해당 tree의 height로 정의하며, union 시 rank가 작아지는 쪽으로 union을 수행한다.
• union & find 시간 :  O(log n)

 

 

# <Find>

public static int find(int x) {
		if(x==parent[x]) return x;
		else return parent[x] = find(parent[x]);
	}

union-find에서 find() 함수로 파라미터로 받은 정수 x의 부모노드를 구하여 출력한다.

== x가 속한 집합 / 그래프의 루트 노드를 반환한다.

 

 

 

# <Union>

	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x!=y) {
			if(x<y) parent[y] = x;
			else parent[x] =y;
		}
	}

union 함수는 x가 속한 집합과 y가 속한 집합을 합친다.

 

 

 

# <isSameParent>

	public static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x==y) return true;
		else return false;
		
	}

isSameParent() 함수는 파라미터로 받은 x와 y의 루트 노드가 같은지 판단한다.

같다면 true, 다르다면 false를 반환하는 bool형 함수이다.

 

 

 

<실행>

public static void main(String args[]) {
		for(int i=1;i<=8;i++) {
			parent[i] = i;
		}
		union(1,2);
		union(2,3);
		union(3,1);
		System.out.println("1과 3은 연결되어 있나요?"+isSameParent(1, 3));
	}

>>반환값 : true

 

 

 

# <전체 코드>

public class Union_Find {
	public static int[] parent = new int[1000001];
	
	public static int find(int x) {
		if(x==parent[x]) return x;
		else return parent[x] = find(parent[x]);
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x!=y) {
			
			
			if(x<y) parent[y] = x;
			else parent[x] =y;
		}
	}
	
	public static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x==y) return true;
		else return false;
		
	}
	public static void main(String args[]) {
		for(int i=1;i<=8;i++) {
			parent[i] = i;
		}
		union(1,2);
		union(2,3);
		union(3,1);
		System.out.println("1과 3은 연결되어 있나요?"+isSameParent(1, 3));
	}
}

 

 

 

 

# Union-Find class

class UFDS {
private:
    vector<int> p, rank, setSizes;
    int numSets;
public:
    UFDS(int N) {
        numSets = N;
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++) p[i] = i;
        setSizes.assign(N, 1);
    }
    int findSet(int i) {
        return (p[i] == i) ? i : p[i] = findSet(p[i]);
    }
    bool isSameSet(int i, int j) {
        return findSet(i) == findSet(j);
    }
    void unionSet(int i, int j) {
        if (!isSameSet(i, j)) {
            int x = findSet(i), y = findSet(j);
            if (rank[x] > rank[y]) {
                setSizes[findSet(x)] += setSizes[findSet(y)];
                p[y] = x;
            } else {
                setSizes[findSet(y)] += setSizes[findSet(x)];
                p[x] = y;
                if (rank[x] == rank[y])
                    rank[y]++;
            }
            numSets--;
        }
    }
    int setSize(int i) {
        return setSizes[findSet(i)];
    }
    int numDisjointSets() {
        return numSets;
    }
};

 

 

참고

https://m.blog.naver.com/parkhj2416/221861837543

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

https://byeong9935.tistory.com/104