느낌표 공장

문제 https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 여기서 주의할 점은 존은 두 쌍 사이의 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 한다. MooTube (Silver) (BOJ 15591)에서는 각 노드마다 BFS를 돌려 ..

Union-Find 란? Disjoint Set을 표현할 때 사용하는 알고리즘 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ? 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호 배타 집합을 표현하는 방법 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연결 리스트보다 효율적이다. 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 상호 배타 집합 연산 m..

def find(x): if par[x] == x: return x else: return find(par[x]) def union(x, y): x = find(x) y = find(y) if rank[x] > rank[y]: par[y] = x elif rank[x] < rank[y]: par[x] = y else: par[y] = x rank[x] += 1 tc = int(input()) for idx in range(1, tc+1): v, e = map(int, input().split()) par = list(range(v+1)) # 루트 rank = [0 for _ in range(v+1)] tmp = [] for _ in range(e): n1, n2, w = map(int, input().s..