C++ [BOJ] 백준 7511번 소셜 네트워킹 어플리케이션

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

7511번: 소셜 네트워킹 어플리케이션

---

SOLUTION

union-find를 활용하는 기본문제.

배열을 이용하여 각 정점의 부모를 찾아 부모가 같으면 두 사람을 연결하는 경로가 있고, 다르면 없음

---

코드

#include <iostream>
using namespace std;

int arr[1000001];

int findParent(int idx) {
	if (arr[idx] == idx) return idx;
	return arr[idx] = findParent(arr[idx]);
}

void merge(int a, int b) {
	int na = findParent(a);
	int nb = findParent(b);
	if (na < nb) arr[nb] = na;
	else arr[na] = nb;
}

void check(int a, int b) {
	int na = findParent(a);
	int nb = findParent(b);
	if (na == nb) {
		cout << 1 << '\n';
		return;
	}
	cout << 0 << '\n';
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;
	for(int i=0;i<tc;i++) {
		int n, k;
		cin >> n >> k;
		for (int j = 0;j < n;j++) {
			arr[j] = j;
		}
		for (int j = 0;j < k;j++) {
			int x, y;
			cin >> x >> y;
			merge(x, y);
		}
		cout << "Scenario " << i + 1 << ":\n";
		int m;
		cin >> m;
		for (int j = 0;j < m;j++) {
			int x, y;
			cin >> x >> y;
			check(x, y);
		}
		cout << '\n';
	}
}