백준 Gold 5 소셜 네트워킹 어플리케이션

소셜 네트워킹 어플리케이션 (백준 Gold 5)

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

특정한 친구 수 N 과
친구 관계에 대한 설명이 k개 주어졌을 때
두 사람이 친구인지 묻는 M개의 질문에 답하는 문제

• 친구라면 1, 아니라면 0을 출력
  

풀이 방법

분리 집합 문제로서
N개의 Parent Vector를 만들고
K개에 대하여 서로 Union 해준 후
M개의 쌍에 대하여 서로 ‘같은 부모’를 가지는 지
검사하면 풀 수 있다!

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int FindParent(vector<int>& pv, int x)
{
	if (pv[x] == x)
		return x;

	return pv[x] = FindParent(pv, pv[x]);
}

bool Union(vector<int>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);

	if (a == b)
		return false;	

	pv[a] = b;

	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	int idx = 1;
	while (idx <= t)
	{
		int n, k;
		cin >> n >> k;

		vector<int> pv(n);
		for (int i = 0; i < n; i++)
			pv[i] = i;

		for (int i = 0; i < k; i++)
		{
			int a, b;
			cin >> a >> b;
			Union(pv, a, b);
		}

		int m;
		cin >> m;

		cout << "Scenario " << idx << ":" << '\n';
		for (int i = 0; i < m; i++)
		{
			int a, b;
			cin >> a >> b;
			if (FindParent(pv, a) == FindParent(pv, b))
			{
				cout << 1 << '\n';
			}
			else
			{
				cout << 0 << '\n';
			}
		}

		cout << '\n';

		idx++;
	}

	return 0;
}

결과

시간 초과인 부분은
아래의 입력 부분에 대한 처리를 빠트려서 발생하였다

ios_base::sync_with_stdio(false);
cin.tie(nullptr);