Baekjoon 4195 친구 네트워크

Link https://www.acmicpc.net/problem/4195

소스결과 4360 KB / 132 ms

출처 Baekjoon, Waterloo's local Programming Contest, 27 September, 2008

언어 C++ 17

분류 해싱, 최소 스패닝 트리, 강한 연결 요소, Disjoint-set, 최대 독립 집합

 

설명

친구를 모으는 것이 취미인 민혁이가 자신의 친구 관계를 줄 때, 두 사람의 친구 네트워크에 현재 몇명이 있는지 구하는 프로그램을 만들어주자.

 

Disjoint-Set을 이용하여 친구 관계를 Tree형태로 저장한다, 또한 입력되는 순서에 따라 결과 값이 다르게 저장된다.

자료형을 직접 String으로 저장하면 비교 연산에서 오랜 시간이 필요하게 된다. 친구이름을 저장하면서 ID를 지정해주는 방식을 사용했다.

 

스터디에서 배우는 내용이기에 Disjoint-Set과 ID를 저장하는 부분은 Class를 사용했다.

 

소스코드

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

class ID {
	map<string, int> ids;

public:
	ID() {};

	void add(string name) {
		if (ids.find(name) != ids.end()) return;
		int id = ids.size() + 1;
		ids.insert(make_pair(name, id));
	}

	int get(string& name) {
		return ids[name];
	}
};

class DisJointSet
{
	int size;
	vector<int> parent;
	vector<int> childs;

public:
	DisJointSet(int size) : size(size) {
		parent.resize(size);
		childs.resize(size);

		for (int i = 0; i < size; i++) {
			parent[i] = i;
			childs[i] = 1;
		}
	};

	int getChilds(int x)
	{
		return childs[find(x)];
	}

	int find(int v) {
		if (parent[v] == v) return v;

		return parent[v] = find(parent[v]);
	}

	bool merge(int x, int y) {

		int px = find(x);
		int py = find(y);

		if (px == py)
			return false;

		parent[px] = py;
		childs[py] += childs[px];

		return true;
	}
};

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

	int tcc;
	cin >> tcc;

	while (tcc--)
	{
		int n;
		cin >> n;

		ID ids;
		DisJointSet dis(2 * n);

		while (n--)
		{
			string a, b;
			cin >> a >> b;

			ids.add(a); ids.add(b);
			dis.merge(ids.get(a), ids.get(b));

			cout << dis.getChilds(ids.get(a)) << '\n';
		}
	}

	return 0;
}