c언어 13306 트리 (백준)

#include <stdio.h>

int find(int x, int* p) { //부분집합의 대표노드 찾기
	if(p[x] == x) return x;
	return p[x] = find(p[x], p);
}

void merge(int x, int y, int* p) { //부분집합 합치기
	x = find(x, p);
	y = find(y, p);
	if(x!=y) p[x] = y;
}

int main(void) {
	int n, q, tmp, tmp_q;
	scanf("%d %d", &n, &q);
	tmp = n+q-1;
	tmp_q = q;
	
	int arr[n+1], parent[n+1], query[tmp][3], ans[tmp];
	
	for(int i=1; i<=n; i++) parent[i] = i; //자신이 속한 집합의 대표노드를 처음엔 자기자신으로 설정
 	for(int i=2; i<=n; i++) scanf("%d", &arr[i]); //간선 입력받기
	for(int i=0; i<tmp; i++) { //쿼리 입력받기
		scanf("%d", &query[i][0]); //0 또는 1
		if(query[i][0] == 0) scanf("%d", &query[i][1]); //1일 경우
		else scanf("%d %d", &query[i][1], &query[i][2]); //0일 경우
	}
	
    //오프라인 쿼리
    //트리를 해체하면서 연결되있는지를 아는 것은 시간이 매우 걸리나
    //역으로 트리를 만들면서 연결되어있는지를 확인하는 것은 union_find을 이용해서 구할 수 있음
    //즉 입력받은 쿼리를 역순으로 실행하면서 이에 대한 대답을 저장한 다음, 다시 쿼리에 대한 결과의 순서를 뒤집어서(원래순서대로) 출력하면 된다.
    
	for(int i=tmp-1; i>=0; i--) { //역순으로 쿼리를 실행 
		if(query[i][0]) { //1일 경우 연결 여부 확인하기
			if(find(query[i][1], parent) == find(query[i][2], parent)) ans[--tmp_q] = 1;
			else ans[--tmp_q] = 0;
		} //0일 경우 간선 잇기
		else merge(query[i][1], arr[query[i][1]], parent);
	}
	
    //결과를 쿼리를 입력받은 순서대로 출력하기
	for(int i=0; i<q; i++) printf("%s\n", (char*[]){"NO","YES"}[ans[i]]);
}

 

풀이 : 오프라인 쿼리, union-find

 

쿼리에는 두 종류가 주어집니다.

0. 간선 끊기

1. 두 노드의 연결여부

 

문제는 만들어진 트리에서 간선을 끊으면서 두 노드의 연결여부를 확인하는 것은 매우 어려우며, 시간이 무척 오래걸립니다.

 

그러나 이를 반대로 뒤집으면

 

0. 간선 연결

1. 두 노드의 연결여부

 

모든 노드가 전부 홀로 있는 상태에서 하나의 트리를 만드는 걸로 바뀌게 됩니다.

이 경우엔 union-find의 분리집합 개념을 이용하면 적은 시간내에 두 노드가 같은 집합에 있는지를 확인하여 간선의 연결 여부또한 알 수 있게 됩니다.

 

즉 노드들을 전부 연결해 놓지 않은 상태에서 쿼리들을 주어진 순서의 역순으로 실행한다면 새로운 트리를 만들면서 적은시간내로 쿼리에 대한 답도 구할 수 있게 됩니다. 이렇게 자신에게 유리한 방식으로 쿼리를 다루는 것을 오프라인 쿼리라고 합니다.

 

 

 

0. union-find을 위한 함수들 생성

1. N, Q을 입력받고 N+Q-1와 Q을 각각 다른 변수를 만들어서 따로 저장해줍니다.

2. 이을 간선을 저장할 배열, 노드가 속한 집합의 대표노드를 가지는 배열, 쿼리를 담을 배열, 쿼리의 결과를 담을 배열을 생성합니다.

3. 노드가 속한 집합의 대표노드를 가지는 배열을 처음에는 자기자신으로 초기화합니다.

4. 간선을 입력 받습니다.

5. 쿼리를 입력 받습니다.

6. 입력받은 쿼리들을 역순으로 실행합니다. 0이면 두 노드를 이어주고, 1이면 두 노드가 연결되어있는지를 확인 한다음 이때의 결과를 다른 배열에 저장합니다.

7. 쿼리의 결과를 처음 쿼리가 입력된 순서대로 출력해줍니다.

 

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

13306번: 트리