[정답이 아니라 풀이 기록입니다.]
트리가 있고 쿼리가 들어온다.
(0 a) : a노드에서 부모와의 연결 된 간선을 제거한다.
(1 a b) : a노드와 b노드를 연결하는 경로가 있는지를 출력한다.
접근
- N-1개의 간선제거 쿼리와 Q개의 연결 여부를 확인하는 쿼리가 들어옵니다.
- 두 노드의 연결 여부는 유니온 파인드로 찾을 수 있지만, 유니온 파인드에서 간선을 제거 하기가 어렵습니다.
- 간선제거의 반대는 간선연결입니다.
구현
간선제거?
문제에서 나온대로 간선을 제거하고 연결 여부를 확인합시다.
연결 여부에서 유니온 파인드를 쓸 수 없기에 탐색을 해야하고, 간선 제거 시간도 있지만 탐색과 제거가 O(N)에 처리 된다고 가정해보면 O(NQ)의 시간이 걸립니다.
N,Q 둘 다 최대가 20만이라 시간초과가 발생합니다.
간선연결!
문제에서 간선의 제거는 총 간선의 개수와 같은 수 만큼 일어납니다.
즉, 모든 쿼리가 끝났을 때 남아있는 간선은 없는 거죠.
그럼 역순으로 모든 간선이 없는 상태로 간선 제거가 들어오면 간선을 연결하면 어떨까요?
간선 제거 -> (간선이 제거된 상태로) 연결 여부 확인
-> (간선이 제거된 상태로) 연결 여부 확인 -> 간선 연결
이렇게 되면 간선의 제거가 아닌 연결만 발생하기에 유니온 파인드를 사용 할 수 있게 됩니다.
그림으로 살펴보죠.
이런 트리가 있다 가정하겠습니다.
쿼리는 총 5개가 들어옵니다.
- 1번 노드와 2번 노드의 연결 여부
- 2번 노드에서 부모와 연결 된 간선 삭제
- 1번 노드와 2번 노드의 연결 여부
- 3번 노드에서 부모와 연결 된 간선 삭제
- 1번 노드와 3번 노드의 연결 여부
출력은 YES, NO, NO 입니다.
이 쿼리들을 역순으로 돌려봅시다.
- 1번 노드와 3번 노드의 연결 여부
- 3번 노드에서 부모와 간선 연결
- 1번 노드와 2번 노드의 연결 여부
- 3번 노드에서 부모와 간선 연결
- 1번 노드와 2번 노드의 연결 여부
출력은 NO, NO, YES 입니다.
답이 역순으로 올바르게 구해집니다.
쿼리를 모두 저장하고, 가장 마지막에 들어온 쿼리부터 실행한 뒤, 답을 역순으로 출력하면 되겠네요!
임의의 쿼리 문제가 있을 때, 보통은 쿼리를 저장하지않고, 들어 온 순간 쿼리의 결과를 바로 구해 출력합니다.
그러나 그것이 어려울 때, 이 문제 처럼 쿼리를 저장해두고 쿼리 입력이 끝난 후 쿼리를 처리하는 것을 오프라인 쿼리라고 합니다.
부모의 정보
이제 구현을 해봅시다.
n-1줄에 거쳐 (2~n)번 노드의 부모가 무엇인지가 들어옵니다.(1번은 루트)
간선을 연결하지 않은 상태로 시작해 쿼리가 들어오면 연결하기에 따로 저장해둡니다.
그리고 저장하는 김에 유니온 파인드에서 쓰이는 parent와 rank도 초기화 시켜줍니다.
int pInfo[200002];
int parent[200002];
int Rank[200002];
for (int i = 2; i <= n; i++) {
scanf("%d",&pInfo[i]);
parent[i] = i;
Rank[i] = 1;
}
parent[1] = 1;
Rank[1] = 1;쿼리의 저장
다음으로 쿼리의 역순 처리를 위해 쿼리를 일단 다 저장해 둬야합니다.
벡터든 스택이든 역순으로 접근하기 편한 곳에 저장해 둡니다.
struct query {
int type;
int node1;
int node2;
query(int a, int b, int c) {
type = a;
node1 = b;
node2 = c;
}
};
for (int i = 1; i < q + n; i++) {
scanf("%d",&num);
if (num == 0) {
scanf("%d",&a);
v.push_back(query(num,a,0));
}
else {
scanf("%d%d",&a,&b);
v.push_back(query(num,a,b));
}
}쿼리의 처리
유니온 파인드를 구현해야하는데, 유니온 파인드는 따로 설명하진 않겠습니다.
int find(int x) {
if (parent[x] == x) {
return x;
}
int y = find(parent[x]);
parent[x] = y;
return y;
}
void merge(int x, int y) {
int a = find(x);
int b = find(y);
if (Rank[a] > Rank[b]) {
parent[b] = a;
Rank[a] += Rank[b];
Rank[b] = 0;
}
else {
parent[a] = b;
Rank[b] += Rank[a];
Rank[a] = 0;
}
}저장해 뒀던 쿼리를 역순으로 접근합니다.
이때 제거 쿼리는 위에서 이야기했듯 간선 연결이기에 유니온 파인드에서 merge로 처리 하고
연결 여부는 find로 확인 해 줍니다.
그리고 답의 역순 출력을 위해 답을 스택에 저장해 둡니다.
stack<int> ans;
for (int i = v.size() - 1; i >= 0; i--) {
if (v[i].type == 0) {
if (find(v[i].node1) != find(pInfo[v[i].node1])) {
merge(v[i].node1, pInfo[v[i].node1]);//간선 연결
}
}
else {
if (find(v[i].node1) != find(v[i].node2)) {
ans.push(0);//연결 안 됨
}
else {
ans.push(1);//연결 됨
}
}
}답 출력
스택에서 꺼내며 답을 출력합니다.
while (!ans.empty()) {
if (ans.top() == 1) {
printf("YES\n");
}
else {
printf("NO\n");
}
ans.pop();
}참고로 유니온 파인드의 시간 복잡도는 경로 최적화와 Rank최적화를 했을 때 연산 당 O(아커만(N))으로 알고 있습니다. 아커만(N)을 상수 취급한다면 이 문제는 O(N + Q) 정도가 소모되겠네요.
마무리
역순 접근이라는 것을 떠올리면 쉽게 풀수있지만, 떠올리는게 어렵습니다.
그리고 이 문제에서 만약 쿼리가 다 끝나고 남아있는 간선이 있다면, 그 간선을 찾아서 미리 merge해야 합니다. 아마 이것 까지 있으면 P3아닐까요?
끝
