취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3261번 문제인 TOWER이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3261 

a번 컵이 포함된 모음과 b번 컵이 포함된 모음이 서로 다른 경우 a→b와 같은 작업을 하면 두 모음이 하나의 모음으로 합쳐지게 된다. 또한 서로 같은 모음에 들어있을 경우 해당 작업으로 컵의 모음이 변하지 않는다.

각 컵을 노드로 생각하고 a→b 작업을 a번 컵 노드와 b번 컵 노드 사이에 에지를 긋는 것으로 생각해보자. 이 때 a번 컵과 b번 컵이 같은 컵 모음에 들어있는지의 여부는 그래프 위에서 서로 같은 component에 속해있는지의 여부로 생각할 수 있음을 알 수 있다.

위의 관찰을 이용하면 각 a→b 연산에 대응되는 에지를 갖는 그래프에서 가장 큰 두 component에 속한 원소를 하나씩 출력하는 것으로 문제를 해결할 수 있음을 알 수 있다.

해당 그래프가 연결그래프여도(component가 유일하더라도) 유효한 move를 출력해주어야 함에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> G[10001];
bool visited[10001];

int dfs(int cur) {
	int ret = 1;
	visited[cur] = 1;
	
	for (auto& nxt : G[cur]) {
		if (visited[nxt]) continue;
		ret += dfs(nxt);
	}

	return ret;
}

int ans1 = 1, cnt1, ans2 = 1, cnt2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		int cnt = dfs(i);
		if (cnt >= cnt1) {
			ans2 = ans1, cnt2 = cnt1;
			ans1 = i, cnt1 = cnt;
		}
		else if (cnt > cnt2) ans2 = i, cnt2 = cnt;
	}

	cout << ans1 << ' ' << ans2;
}