演算法›Ch4 圖論演算法第 73 題/共 111 題
73. Union-Find、Path Compression
#AL-04-073易Union-FindPath Compression
The following C code is provided. Analyze the functionality of the code and answer the question.
#include <stdio.h>
int operation1(int parent[], int x) {
if (parent[x] != -1) {
int rootX = operation1(parent, parent[x]);
parent[x] = rootX;
return rootX;
}
return x;
}
void operation2(int parent[], int x, int y) {
int rootX = operation1(parent, x);
int rootY = operation1(parent, y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
int main() {
int parent[6] = {-1, -1, -1, -1, -1, -1};
parent[2] = 1;
parent[3] = 2;
parent[4] = 3;
operation1(parent, 4);
operation2(parent, 1, 3);
operation2(parent, 5, 4);
for(int i=0; i<=5; i++){
printf("%d ", parent[i]);
}
return 0;
}
Which of the following statements is correct?
📄 成大114
▤完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法