CSES 4. Road Construction (1676)

출처: https://cses.fi/problemset/task/1676

---

문제 설명

There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

입력 

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n 

Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

출력

Print m lines: the required information after each day.

입력 예

5 3
1 2
1 3
4 5

출력 예

4 2
3 3
2 3

제약조건

• 1 <= n < 1e5
• 1 <= m < 2 * 1e5
• 1 <= a, b <= n

---

문제 풀이

connected component count & component size 를 찾는 문제이다. 그래프에서 connected component를 찾는 방법은 DFS, BFS, Union find 등의 방법을 사용한다. 전체 node를 검사하는 경우 시간복잡도는 O(nm)) 이지만, n=1e5, m=2x1e5 의 입력에서 시간초과가 나오므로, 중간에 계산량을 줄이는 방법이 필요해진다.

이 문제는 road(edge)가 추가되므로 추가된 부분과 연결된 부분만 계산한다. 

 

즉, 모든 edge를 검사할 필요 없이, 이번에 추가되는 edge와 연결된 vertex들에 대해서, 같은 component에 있는 지 확인하고, 있다면 component 숫자나 최대 크기를 변경할 필요가 없고, 서로 다른 component에 있는 경우에는 component 숫자를 줄이고, 새롭게 만들어진 component 크기와 원래 최대 크기를 비교해서 최대크기를 갱신하면 된다.

프로그램 내용

...
int cnt = n;				/// number of components 
for (int i = 0; i < m; i++)
{
	int a, b;
	cin >> a >> b;

	if( find_root(a) != find_root(b))
	{
		join(a, b);			/// component merge & max_sz update
		cnt--;				/// number of components decrease
	}

	cout << cnt << " " << max_sz << "\n";
}
...

 

Graph Algorithms ( link )