출처 : https://www.acmicpc.net/problem/17398 풀이 방법풀이의 방법만 안다면 구현은 간단한 문제였다. 간선을 하나씩 끊어 가면서 이때 나누어진 두 집합의 노드의 수를 계산하는 문제이다.만약 간선을 끊을 때마다, 끊어진 두 노드에서 bfs 또는 dfs를 수행해서 각 집합의 노드의 수를 계산하게 된다면 시간 복잡도가 초과된다.그렇게 때문에 nlogn 이하의 시간 복잡도를 가지는 알고리즘을 생각해 내야 했다. 지금 까지 공부하며 시간 복잡도를 줄였던 방법에 대해 생각해 보았다. 1. 노드기준이 아닌 엣지 기준으로 생각해 보기2. 방향 간선에선 간선의 방향을 바꾸어 보기3. 순서를 역으로 생각해 보기 등등 생각이 났지만, 이 문제에 적용할 수 있는 방법은 역으로 생각하기였다. 1...