CodeAngie

문제 N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다. 이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때, 어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다. 풀이 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다. 즉 모두 같은 부모 노드를 갖고 있다는 의미이다. 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다. 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다. 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다. Union-Find 알고리즘을 사용해 두 개의 분리된..