Submitted Code

Python

N, M = map(int, input().split())
from_nodes = [i for i in range(N + 1)]
from_groups = {i: [i] for i in range(1, N + 1)}
from_groups2edges = [0] * (N + 1)
for _ in range(M):
	node1, node2 = list(map(int, input().split()))	
	p_node1 = from_nodes[node1]
	p_node2 = from_nodes[node2]
	if p_node1 == p_node2:
		from_groups2edges[p_node1] += 1
		continue
	p_min, p_max = min(p_node1, p_node2), max(p_node1, p_node2)
	for n in from_groups[p_max]:
		from_nodes[n] = p_min
	from_groups[p_min] += from_groups[p_max]
	from_groups[p_max] = []
	from_groups2edges[p_min] += (from_groups2edges[p_max] + 1)
	from_groups2edges[p_max] = 0
	
result = (0, N, N)
for node_num, nodes in from_groups.items():
	component = len(nodes)
	density = from_groups2edges[node_num] / max(component, 1)
	tmp = (-density, component, node_num)
	if result > tmp:
		result = tmp

answer = sorted(from_groups[result[2]])
print(' '.join(map(str, answer)) + ' ')

Challenge Review

그래프 문제를 풀 수 있는 방법이 여러 개라는 걸 알았다. 다른 방법으로도 풀어봐야겠다.