演算法›Ch4 圖論演算法
第 73 題/共 111 題
◀ AL 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 圖論演算法
本章題號 · 61–80 / 111