📖 Codeforces Round 998 E : https://codeforces.com/contest/2060/problem/E

E. Graph Composition

두 개의 간단한( self-loop나 중복 간선이 없는 ) 무방향 그래프 (F)와 (G)가 주어진다. 두 그래프는 모두 (n)개의 정점을 가지고 있으며, (F)는 (m_1)개의 간선을, (G)는 (m_2)개의 간선을 갖는다. 정점은 (1)부터 (n)까지 번호가 매겨져 있다.

다음 두 종류의 연산을 아무 번이나 할 수 있다:

1. 간선 제거 연산
   (F)에 존재하는 간선 ((u, v))를 골라서 제거한다.
   ((1 <= u, v <= n), ((u, v))는 (F)에 존재하는 간선)

2. 간선 추가 연산
   (F)에 없는 간선 ((u, v))를 골라서 추가한다.
   ((1 <= u, v <= n), ((u, v))는 (F)에 없는 간선)

이 연산들을 통해, 임의의 두 정점 (u, v) ((1 <= u, v <= n))에 대하여,

• (F)에서 (u)에서 (v)로 가는 경로가 존재하면, (G)에서도 (u)에서 (v)로 가는 경로가 존재하고,
• (G)에서 (u)에서 (v)로 가는 경로가 존재하면, (F)에서도 경로가 존재하도록,

즉, (F)와 (G)가 같은 연결 상태를 갖도록 만들고자 한다.

위 조건을 만족하기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 테스트 케이스의 개수 (t) ((1 <= t <= 10^4))가 주어진다.

이후 (t)개의 테스트 케이스가 주어지며, 각 테스트 케이스마다 아래의 정보를 포함한다:

1. 첫 줄에 정수 (n, m_1, m_2)가 공백으로 주어진다.

   • (1 <= n <= 2*10^5)
   • (0 <= m_1, m_2 <= 2*10^5)

2. 다음 (m_1)개의 줄에 걸쳐, 그래프 (F)의 간선을 나타내는 두 정수 (u, v)가 주어진다.
   ((1 <= u, v <= n))
   이는 (F)에 ((u, v)) 간선이 존재함을 의미한다. 중복 간선이나 self-loop는 없다.

3. 이어서 (m_2)개의 줄에 걸쳐, 그래프 (G)의 간선을 나타내는 두 정수 (u, v)가 주어진다.
   ((1 <= u, v <= n))
   이는 (G)에 ((u, v)) 간선이 존재함을 의미한다. 중복 간선이나 self-loop는 없다.

제한

• 모든 테스트 케이스를 통틀어 (sum(n)), (sum(m_1)), (sum(m_2))는 각각 최대 2*10^5를 넘지 않는다.

---

출력

각 테스트 케이스마다, 그래프 (F)를 연산(간선 제거·추가)을 통해 그래프 (G)와 연결 상태가 동일해지도록 만들기 위해 필요한 최소 연산 횟수를 한 줄에 출력한다.

---

풀이

 주어진 그래프 F를 G와 동일한 연결상태로 만드는 최소 연산 횟수를 출력해야 한다. F에서 한 간선을 없애거나 추가하는 연산 횟수의 최소를 구하는 문제이다. 각 그래프의 연결상태를 DSU를 활용해 표현하고 G와 F의 집합을 비교해서 그 차이를 구해내는 방식으로 풀 수 있다. G의 그래프로 표현할 수 있는 집합들과 F의 그래프로 표현할 수 있는 집합들 간의 차이점을 찾아 추가해야하는 간선과 제거해야하는 간선의 개수를 찾는 것이 이 풀이의 골자이다.

 먼저 G의 집합을 만들고 입력받은 F의 간선들을 차례로 꺼내어 G의 집합과 동일하게 만들 수 있는지 체크한다. 만약 동일하게 존재하는 집합의 원소라면 F도 마찬가지로 집합을 만들어 나간다. 존재하지 않는 집합의 원소라면 wrongEdge의 개수를 늘리고 집합으로 추가하지 않는다. 이 연산을 마치고 나면 F는 G와 동일하게 집합을 이루고 있는 노드들만 자신의 집합으로 만들어졌을 것이고, G와 다른 간선의 개수를 알고 있는 상태가 된다. 즉, wrongEdge의 값이 F에서 지워야하는 간선의 개수가 된다.

 마지막으로 F와 G의 집합의 개수를 비교해 F에 추가해줘야하는 간선의 개수를 찾는다. F의 집합의 개수 - G의 집합의 개수가 F에 추가해줘야하는 간선의 개수가 된다. 지워야하는 간선의 개수와 추가해줘야하는 간선의 개수를 더해서 최소 연산 횟수를 찾아낼 수 있다.

---

코드

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

struct union_find {
	vector<int> parent, sz;
	int components;

	union_find(int n) {
		init(n);
		components = n;
	}

	void init(int n) {
		parent.resize(n + 1);
		iota(parent.begin(), parent.end(), 0);
		sz.assign(n + 1, 1);
	}

	int Find(int x) {
		if (x == parent[x]) return x;
		return parent[x] = Find(parent[x]);
	}

	void Union(int x, int y) {
		x = Find(x);
		y = Find(y);

		if (x == y) return;

		if (sz[x] < sz[y]) swap(x, y);
		sz[x] += sz[y];
		sz[y] = 0;
		parent[y] = x;

		components--;
	}

	bool isUnion(int x, int y) {
		return Find(x) == Find(y);
	}
};

void solve() {
	int u, v;
	int n, m1, m2;
	cin >> n >> m1 >> m2;
	vector<pair<int, int>> F;

	union_find uf_G(n), uf_F(n);

	for (int i = 0; i < m1; i++){
		cin >> u >> v;
		F.push_back({ u,v });
	}

	for (int i = 0; i < m2; i++) {
		cin >> u >> v;
		uf_G.Union(u, v);
	}

	int wrongEdge = 0;

	for (int i = 0; i < m1; i++) {
		if (uf_G.isUnion(F[i].first, F[i].second)) {
			uf_F.Union(F[i].first, F[i].second);
		}
		else {
			wrongEdge++;
		}
	}
	int ans = wrongEdge + uf_F.components - uf_G.components;
	cout << ans << '\n';
}

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

	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}