글 읽기 - union-find 시간을 어떻게 줄여야 할지 모르겠어요..

jh1125kr 7년 전 0

다른 분 소스를 봐도 비슷한 것 같은데 왜 시간초과가 나는지 모르겠어요 ㅠㅠ

for (q = a; (p = parent[q]) >= 0; q = p);
  s = q;
  for (q = a; (p = parent[q]) >= 0; q = p)
  {
   parent[q] = s;
  }

이부분은 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 하려고 만들어서

더 시간을 줄이려고 만든건데

왜 시간이 초과되는지 모르겠습니다 ㅠㅠ

#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>

using namespace std;

int parent[1000001];
int num[1000001];

void set_init()
{
	for (int i = 0; i <= 1000000; i++)
	{
		parent[i] = -1;
		num[i] = 1;
	}
}

int set_find(int v)
{
	int p, s, i = -1;
	for (i = v; (p = parent[i]) >= 0; i = p);
	s = i;
	for (i = v; (p = parent[i]) >= 0; i = p)
	{
		parent[i] = s;
	}
	return s;
}

void set_union(int s1, int s2)
{
	if (num[s1] < num[s2])
	{
		parent[s1] = s2;
		num[s2] += num[s1];
	}
	else
	{
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	set_init();
	for (int i = 0; i < m; i++)
	{
		int check, a, b;
		scanf("%d %d %d", &check, &a, &b);

		int uset, vset;

		if (check == 0) // a와 b를 합친다.
		{
			if (a != b)
			{
				uset = set_find(a);
				vset = set_find(b);
				set_union(uset, vset);
			}
		}
		else // check==1 a와 b가 같은 집합인지 확인한다. YES/NO로 판별.
		{
			if (a!=b)
			{
				uset = set_find(a);
				vset = set_find(b);
				if (uset == vset)
				{
					printf("YES\n");
				}
				else
				{
					printf("NO\n");
				}
			}
			else
			{
				printf("YES\n");
			}
		}
	}
}

smu201111192 7년 전 0

유니온 함수 부분이 좀 비효율적인거같습니다. 경로압축을 사용해보세요

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

문제

문제

출처

ICPC

union-find 시간을 어떻게 줄여야 할지 모르겠어요..

jh1125kr 7년 전 0

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말