백준 20955

아이디어

문제에서 말하는

사이클이 없는 그래프인 트리를 위한 edge의 삭제, 추가 횟수를 구하려면

다음과 같은 순서를 거쳐야 한다

 

1. 주어진 edge 중에서 사이클을 생성하는 edge를 다 쳐낸다

2. 주어진 edge로 만들어지는 그룹의 개수를 구한다

3. 쳐낸 edge 수 + 그룹 개수 - 1이 답이 된다

 

1번은 MST의 Kruskal 알고리즘에서 나오는 union find 알고리즘을 통해서,

2번은 DFS로 구하면 된다

union find 알고리즘을 처음 구현해봐서 포스팅하게 되었다.

 

코드

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

int N, M;
vector<vector<int>> E;
bool visited[100000];
int groupCount = 0;
int root[100000];
int depth[100000];
int cycleEdgeCount = 0;

void DFS(int n, bool isFirstAccess) {
	if (visited[n])
		return;

	visited[n] = true;
	int s = E[n].size();
	for (int i = 0; i < s; i++)
		DFS(E[n][i], false);

	if (isFirstAccess)
		groupCount++;

	return;
}

int unionSet() {
	for (int i = 0; i < N; i++) {
		root[i] = i;
		depth[i] = 1;
	}

	return 0;
}

int unionFind(int n) {
	if (root[n] == n)
		return n;
	else
		return root[n] = unionFind(root[n]);
}

int unionOperation(int a, int b) {
	int x = unionFind(a);
	int y = unionFind(b);

	if (x == y)
		return 0;

	if (depth[x] > depth[y])
		root[y] = x;
	else if (depth[x] < depth[y])
		root[x] = y;
	else {
		depth[y]++;
		root[x] = y;
	}
	
	return 0;
}

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

	scanf("%d", &N);
	fill_n(visited, N, false);
	scanf("%d", &M);
	E = vector<vector<int>>(N, vector<int>());

	unionSet();
	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d", &a);
		a--;
		scanf("%d", &b);
		b--;
		if (unionFind(a) == unionFind(b))
			cycleEdgeCount++;
		else 
			unionOperation(a, b);

		E[a].push_back(b);
		E[b].push_back(a);
	}

	for (int i = 0; i < N; i++)
		DFS(i, true);

	printf("%d", groupCount - 1 + cycleEdgeCount);

	

	return 0;
}

노드가 최대 10만개라서 엣지를 2차원 배열로 표기하게 되면 배열이 너무 커져서 벡터를 사용했다

값을 입력받으면서 cycle 여부를 확인하고

다 입력받은 뒤 DFS를 돌려서 그룹의 개수를 구한다

 

union find 알고리즘의 경우

unionFind에서 root를 찾아 올라가는 과정에서 만나는

모든 노드들을 루트 노드에다가 붙이는 최적화(return root[n] = unionFind(root[n]))랑

unionOperation에서 항상 depth가 낮은 트리를 더 높은 트리의 루트에 갖다가 붙이는 최적화(if 문)를 했다

이 문제에서 최적화를 안해도 통과할 수 있는지는 모르겠다