백준 24391번 귀찮은 해강이 C++

출처 : https://www.acmicpc.net/problem/24391

유니온 파인드

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;
vector<int> height;

int GetParent(int n) {
	if (n == parent[n]) return n;
	return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
	u = GetParent(u);
	v = GetParent(v);

	if (u == v) return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

int n, m;

int main()
{
	cin >> n >> m;
	parent = vector<int>(n + 1);
	height = vector<int>(n + 1, 1);
	for (int i = 1; i <= n; i++)
		parent[i] = i;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Merge(a, b);
	}

	int curr;
	cin >> curr;
	int ans = 0;
	for (int i = 1; i < n; i++) {
		int next;
		cin >> next;
		if (GetParent(curr) != GetParent(next))
			ans++;
		curr = next;
	}
	cout << ans;
}