[백준 4195] 친구 네트워크

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

4195번: 친구 네트워크

 

요구사항

주어진 2명의 친구 네트워크의 총합을 출력한다

 

풀이

1. 해싱을 이용해 이름을 저장한다

2. hash_size를 고유 값으로 받는다

3. 두 이름을 disjoint하여 부모 값을 찾는다

 

#include <iostream>

using namespace std;
const int HASH_SIZE = 10000;
const int PN = 23;
int table[10000][100];
char hash_raw[100001][30];

int hash_size = 0;
int parent[100001];
int num[100001];
unsigned int get_key(char str[]) {
	unsigned int key = 0, p = 1;
	for (int i = 0; str[i] != 0; i++) {
		key += (str[i] * p);
		p *= PN;
	}
	return key%HASH_SIZE;
}
void add(char str[]) {
	unsigned int key = get_key(str);
	int i = 0;
	for (i = 0; str[i] != 0; i++) {
		hash_raw[hash_size][i] = str[i];
	}
	hash_raw[hash_size][i] = 0;

	int &size = table[key][0];
	table[key][++size] = hash_size++;
}
int my_strcmp(char a[], char b[]) {
	int i = 0;
	int j = 0;
	while (a[i]) {
		if (a[i++] != b[j++]) {
			i--, j--;
			break;
		}
	}
	return a[i] - b[j];
}
int contain(char str[]) {
	unsigned int key = get_key(str);
	int size = table[key][0];
	for (int i = 1; i <= size; i++) {
		int pos = table[key][i];
		if (my_strcmp(hash_raw[pos], str) == 0) {
			return pos;
		}
	}
	return 0;
}
int Find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = Find(parent[x]);
}

int Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	//cout << "FF" << endl;
	if (x < y) {
		parent[x] = y;
		num[y] += num[x];
		num[x] = 1;
		return num[y];
	}
	else if (x>y){
		parent[y] = x;
		num[x] += num[y];
		num[y] = 1;
		return num[x];
	}
	else {
		return num[x];
	}
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		int n;
		scanf("%d", &n);
		hash_size = 0;
		for (int i = 0; i < 10000; i++) {
			table[i][0] = 0;
		}
		for (int i = 0; i <= n; i++)
		{
			parent[i] = i;
			num[i] = 1;
		}

		for (int i = 0; i < n; i++)
		{
			char ch1[21], ch2[21];
			scanf(" %s %s", ch1, ch2);
			int a = contain(ch1);
			int b = contain(ch2);
			if (a == 0) {
				add(ch1);
				a = contain(ch1);
			}
			if (b == 0) {
				add(ch2);
				b = contain(ch2);
			}
			//	cout << "A" << endl;
			//	cout << "A" << a << "B" << b << endl;
			printf("%d\n", Union(a, b));

		}
	}
}