글 읽기 - stl 없이 풀려고 하니까 안되네요.ㅜ

na982 6년 전 0

stl map을 이용해서는 풀었는데,

has를 이용해서 아래와 같이 문제를 풀었는데 틀렸다고 나오네요;

아마도 has를 잘못 쓰거나 어디서 놓치는 부분이 있는것같은데 잘 모르겠네요;

도움 부탁 드립니다.

#include <stdio.h>
#include <string.h>

const unsigned int PN = 23;

int key[1000000], u[1000000], cnt[1000000];
unsigned int get_key(char* name) {
	unsigned int ret = 0, p = 1;
	for (int i = 0; name[i] != 0; ++i) {
		ret = (ret + (p * name[i]));
		p *= PN;
	}
	return (ret % 1000000);
}

int has_friend(char* name) {
	unsigned int c = get_key(name);
	if (key[c] == 1)		return 1;
	else					return 0;
}

void add_friend(char* name) {
	unsigned int c = get_key(name);
	key[c] = 1;
}

int find_root(int n) {
	if (u[n] == n)		return n;
	else				return u[n] = find_root(u[n]);
}

int main()
{
	int tc, n;
	scanf("%d", &tc);
	while (tc--) {
		memset(key, 0, sizeof(key));
		for (int i = 0; i < 1000000; ++i)	u[i] = i, cnt[i] = 1;

		char a[21], b[21];
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) {
			scanf("%s %s", a, b);
			
			if (!has_friend(a)) {
				add_friend(a);
			}

			if (!has_friend(b)) {
				add_friend(b);
			}

			int ra = find_root(get_key(a));
			int rb = find_root(get_key(b));

			if (ra != rb) {
				u[ra] = rb;
				cnt[rb] += cnt[ra];
			}

			printf("%d\n", cnt[rb]);
		}
	}
	return 0;
}

naong606 6년 전 0

서로 다른 이름의 hash값이 충돌하는 경우에 제대로 동작하지 않을 것 같습니다.

get_key(a)와 get_key(b)가 같게 되는 경우, ra == rb가 되어 56~59의 조건문이 수행되지 않을 것 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

stl 없이 풀려고 하니까 안되네요.ㅜ

na982 6년 전 0

naong606 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말