tree5 [백준][union find] 13244 Tree c++구현 목차 https://www.acmicpc.net/problem/13244문제문제 설명컴퓨터 과학에서 가장 중요한 자료 구조 중 하나는 트리입니다. 이 문제에서는 일반적인 트리에 대해 다룹니다.트리는 다음 세 가지 속성을 가지는 그래프의 부분 집합입니다:연결성 (Connected): 모든 노드에 대해, 한 노드에서 다른 모든 노드로 가는 경로가 존재합니다.간선 제거 시 비연결성 (Edge removal leads to disconnection): 한 간선을 제거하면, 그래프는 더 이상 연결되지 않습니다. 즉, 일부 노드에 도달할 수 없게 됩니다.간선 추가 시 순환 생성 (Edge addition creates a cycle): 기존의 두 노드 A와 B 사이에 간선을 추가하면 순환이 생성됩니다. 즉, A에서.. 2024. 7. 29. [백준][크루스칼] 1197 최소 스패닝 트리 c++ 구현 목차 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 보기 전에 참고하면 좋을 것 같습니다 https://be-senior-developer.tistory.com/29 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs,.. 2024. 2. 22. [백준][union find] 1717 집합의 표현 c++ 구현 목차 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 보기 전에 참고하면 좋을 것 같습니다 https://be-senior-developer.tistory.com/29 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를.. 2024. 2. 22. [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를 돌리는 것은 비효율적이므로 자기 그룹의 꼭대기에 있는 사람만 비교하는 것이다. 2와 8은 다른 그룹인 것을 알 수 있다. 트리에 값 추가하는 방법 parent[2] = 3; parent[7] = 3; parent[5] = 3; parent[8] = 4; 두 수가 같은 집합인지 알기 위해 필요한 함수 int find_root(int node) { if (parent[node].first == node) return node; //노드의 최적화: 항상 부모를 루트노드로 만듬 return parent[node] = fi.. 2024. 2. 22. 이전 1 2 다음 728x90
