📚 알고리즘/유니온파인드(Union-Find)

[백준 1717] 집합의 표현_union-find(c++)

[문제] https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net [문제풀이] n개의 수와 m개의 연산을 입력으로 받는다 m개의 줄에는 각각의 연산이 주어지는에 첫번째 숫자가 0 이면 union연산을 첫번째 숫자가 1이면 find연산을 하면된다 find연산을 할때, 두개의 숫자가 같은 부모노드를 가지고 있다면 YES를 아니라면 NO를 출력하면 된다 [전체코드] #include #include using namespa..

[백준 1976] 여행가자_union_find(C++)

유니온 파인드란? 그래프 알고리즘의 일종이다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은집합에 있는지 확인하는 알고리즘이다. 또한 여러 노드가 존재할 때, 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 있는지의 여부를 판별하는 알고리즘. find 연산 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union 연산 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 서로소 집합(disjoint Set)그리고 병합 찾기 집합(merge find set) 이라 고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조 참고사이트 : https://brenden.tistory.com/33 [문제] https://www.acm..