반응형 유니온파인드2 (Python/🥇4)백준알고리즘 4803번 : 트리 문제 바로가기 문제:그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.입력:입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두.. 2024. 9. 26. Union-Find (Disjoint Sets) 알고리즘 Union - Find랑 크루스칼 알고리즘을 사용하려면 필수적으로 알아야하는 알고리즘이다. 여러개의 노드가 존재할때 두 개의 노드를 선택하여 같은 트리에 포함되어있는지 확인하는 것이다. Union - Find 를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. 트리로 부분집합을 표현하고 find를 통해 루트 노드를 찾고 union으로 트리를 합친다. 처음 시작할때 숫자들은 자기 자신이 부모이며, 노드가 연결되어있어 합치게 되면 더 작은값이 부모가 된다. 만약 1,2 가 연결되어있으면 부모는 1,1 이다. def find(parent, x): if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우 parent[x] = find(parent, parent[x]) retur.. 2023. 6. 13. 이전 1 다음 반응형
