[leetcode] 684. Redundant Connection

문제 : https://leetcode.com/problems/redundant-connection/

---

n개의 노드와 n개의 간선으로 이루어진 무방향 그래프가 주어질 때,

n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선을 구하여라.

---

조건에 그래프들은 연결되어 있고 노드가 n개인데 간선도 n개라고 하니, 트리의 특징 중 하나인 간선의 개수는 정점 개수 - 1 이다.를 생각하면 정답이 되는 간선은 1개가 나올 수 있고. 이 간선은 사이클을 만듬을 알아낼 수 있다.

크루스칼 알고리즘 구현에서 사이클이 생성됨을 알아내기 위해 유니온 파인드를 사용했었다.

이를 응용하여, 입력으로 주어지는 간선들을 Union-Find 의 Union 연산으로 하나의 집합으로 합치면서 이미 같은 집합인데 Union 연산의 하는 경우를 찾아낸다. 이 경우, 해당 간선이 사이클을 만드는 경우인 걸 알수 있고 해당 간선이 정답이 된다.

 

시간복잡도는 O(N). 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/684.%20Redundant%20Connection.cpp