글 읽기 - 유니온 파인드 문제를 그래프로 풀었는데 시간초과가 납니다. 이해가 안됩니다.

minjun623 3년 전 0

만약 a개와 b개의 집합을 합칠 경우, 시간 복잡도는 O(min(a, b)) 입니다.

집합 합치는 연산을 10만번까지 할수 있으니, 제가 생각하는 최악의 시간 복잡도를 적어보겠습니다.

s(a) + s(b) 를 집합 크기가 각각 a, b 인 집합을 합치는거라고 정의하면.

s(1) +s(1), ~, s(1) + s(1) 갯수 총 5만개

s(2) + s(2), ~ s(2) + s(2) 갯수 총 2만 5천개

s(4) + s(4) ~ s(4) + s(4) 갯수 총 1만 2500개

s(50000) + s(50000) 갯수 총 1개

1*50000 + 2*25000 + 4*12500 + 8*6250 + ~ 50000*1 << 10^8이라고 생각 됩니다.

왜 시간초과가 뜨는지 이해하지 못했습니다.

도와주세요.

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int N, M, memo_size[1000001], memo_id[1000001];

vector<vector<int> > graph(1000001);

void comb(int a, int b){
	int i, qs, x;
	if(memo_size[a] < memo_size[b]){// a>b
		comb(b, a);
	}else if(a!=b){
		memo_id[b] = memo_id[a];
		queue<int> q;
		q.push(b);
		qs = 1;
		while(qs){
			x = q.front();
			q.pop();
			qs--;
			for(i=0; i<graph[x].size(); i++){
				if(memo_id[graph[x][i]] != memo_id[a]){
					memo_id[graph[x][i]] = memo_id[a];
					q.push(graph[x][i]);
					qs++;
				}
			}
		}
		graph[a].push_back(b);
		graph[b].push_back(a);
		memo_size[a] += memo_size[b];
	}
	return;
}
int main(void){
	int i, x, a, b;
	scanf("%d%d", &N, &M);
	for(i=0; i<=N; i++){
		memo_size[i] = 1;
		memo_id[i] = i;
	}

	for(i=0; i<M; i++){
		scanf("%d%d%d", &x, &a, &b);
		if(x){
			printf("%s\n", memo_id[a] == memo_id[b] ? "YES" : "NO");
		}else{
			comb(a, b);
		}
	}
	return 0;
}