[BOJ] 4195 친구 네트워크 [map 구현]

문제: https://www.acmicpc.net/problem/4195

 

 

문제 풀이:

map과 union find를 이용하여 쉽게 풀 수 있는 문제이다.

 

 

소스 코드:

stl unordered_map사용

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <unordered_map>
#include <algorithm>
using namespace std;

int p[200001],cnt[200001];
string name1,name2;


int find(int n)
{
	if (p[n]==n) return n;

	return p[n] = find(p[n]);
}

int merge(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
	{
		p[b] = a;
		cnt[a] += cnt[b];
		cnt[b] = 1;
	}
	return cnt[a];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc, n, temp=0;
	cin >> tc;

	while (tc--)
	{
		unordered_map<string, int> m;
		cin >> n;
		for (int i = 0; i < 2 * n + 1; i++) p[i] = i, cnt[i] = 1;
		for (int i = 0; i < n; i++)
		{
			cin >> name1 >> name2;
			
			if (m.count(name1) == 0) m[name1] =temp++;
			if (m.count(name2) == 0) m[name2] = temp++;
			cout << merge(m[name1], m[name2])<<'\n';
		}
	}
	return 0;
}

 

 

map 구현

#include <iostream>
#define HASHMAX 1000007
#define div2 17
using namespace std;

int tc, n, cnt, p[HASHMAX];

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
int merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		p[a] += p[b];
		p[b] = a;
	}
	return -p[a];
}
struct item {
	char key[22];
};

item arr[HASHMAX];

void init() {
	for (int i = 0; i < HASHMAX; i++) {
		arr[i].key[0] = '\0';
		p[i] = -1;
	}
}
int _strlen(char input[]) {
	int i = 0;
	while (input[i] != '\0') {
		i++;
	}
	return i;
}

//문자열을 정수로 변환
int convert(char str[]) {
	int ret = 401;
	int len = _strlen(str);
	for (int i = 0; i < len; i++) {
		ret = ((ret << 4) + (int)(str[i])) % HASHMAX;
	}
	return ret % HASHMAX;
}

// 문자열 같은지 비교
bool compare(char a[], char b[]) {
	int i = 0;
	while (a[i] != '\0' &&b[i]!='\0') {
		if(a[i] != b[i]) return false;
		i++;
	}
	if (a[i] != '\0' || b[i] != '\0') return false;
	else return true;
}

int insert(char str[]) {
	int key = convert(str);
	int p2 = (div2 - key) % div2;
	if (p2 <= 0) p2 += div2;

	int p = key;
	while (arr[p].key[0] != '\0') {
		if (compare(arr[p].key,str)) return p;
		p = (p + p2) % HASHMAX;
		if (p == key) break;
	}
	int i = 0;
	while (str[i] != '\0') {
		arr[p].key[i] = str[i];
		i++;
	}
	arr[p].key[i] = '\0';
	return p;
}


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

	cin >> tc;
	while (tc--) {
		init();
		cin >> n;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			char c1[22], c2[22];
			cin >> c1 >> c2;
			int p1 = insert(c1);
			int p2 = insert(c2);
			cout << merge(p1, p2) << '\n';
		}
	}

	return 0;
}