[zerojudge] c463: apcs 樹狀圖分析 (Tree Analyses)

6月 18, 2020

[zerojudge] c463: apcs 樹狀圖分析 (Tree Analyses)

題目連結：

c463: apcs 樹狀圖分析 (Tree Analyses)

題意：

給定一顆 $n$ 個節點的有根樹$(rooted \ tree)$，

求出根節點編號和每一個節點的高度總和。

解題策略：

關於樹的基本概念：

每個節點都只有有限個子節點或無子節點。
每個節點只會被一個子節點指向。
不會出現環。

關於根節點：

一棵樹只會有一個根節點。
沒有父節點的節點稱為根節點。

根節點求法：

對於每個節點資訊，

紀錄其子節點和父節點編號，

最後從頭跑一次，

沒有父節點的節點即為根節點。

樹高總和求法：

有兩種求法：

從葉節點往上找。
從根節點深度優先搜尋$(DFS)$。

程式碼參考：

$Method \ 1.$：

因為要求高度，

只要從葉節點往上找就好。

要特別注意的是經過這個節點時紀錄的高度，

可能不是最大高度，

因此每次經過時要取最大高度，

跑完之後總和即為所求。

$C++$：

$JUDGE\_RESULT$：$AC \ (0.2s, 1.5MB)$

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;

class Tree {
private:
    struct node {
        int parent, height; // 父節點, 高度
        bool isleaf; // 是否為葉節點
        node(): parent(0), height(0), isleaf(true) {}
    };

    vector<node> v; // 存取節點資料

    void h(node* cur) { // 計算高度
        int sum = 0;
        while (cur->parent) { // 如果還有父節點
            cur = &v[cur->parent]; // 往上找
            sum++;
            cur->height = max(cur->height, sum); // 取最高的高度
        }
    }

public:
    int root; // 根節點
    void update(int num, int val) {
        v[num].isleaf = false; // 不為葉節點
        v[val].parent = num; // 紀錄父節點
    }

    void find_root() { // 尋找根節點
        // 因為根節點不會有父節點
        // 所以找到 parent 為零的即為根節點
        for (int i = 1; i < v.size(); i++) {
            if (!v[i].parent) {
                root = i;
                break;
            }
        }
    }

    long long H() { // 計算高度總和
        for (int i = 1; i < v.size(); i++)
            if (v[i].isleaf) // 從葉節點找就好
                h(&v[i]);
        long long sum = 0;
        for (int i = 1; i < v.size(); i++) // 總和高度
            sum += v[i].height;
        return sum;
    }

    Tree(int n = 0): root(-1) {
        v.resize(n);
    }
};

int main() { _
    int N, K, tmp;
    cin >> N;
    Tree tree(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> K;
        while (K--) {
            cin >> tmp;
            tree.update(i, tmp);
        }
    }
    tree.find_root();
    cout << tree.root << endl;
    cout << tree.H() << endl;
}

$Method \ 2.$：

從根節點開始深度優先搜尋$(DFS)$，

對該節點的每一個子節點遞迴，

並記錄最大高度，

當層高度即為「子樹最大深度 - 當前深度」，

跑完之後，總和即為所求。

$C++$：

$JUDGE\_RESULT$：$AC \ (36ms, 10MB)$

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;
class Tree {
private:
    struct node {
        int parent, height; // 父節點，高度
        vector<int> child; // 子節點
        node(): parent(0), height(0) {}
    };
    vector<node> v; // 存取節點資料
    int dfs(int cur, int dep = 0) {
        if (!v[cur].child.size()) // 為葉節點
            return dep; // 回傳當前深度
        int maxheight = 0; // 最大深度
        for (auto& i : v[cur].child) { // 對每一個子節點遞迴
            int tmp = dfs(i, dep + 1);
            maxheight = max(maxheight, tmp); // 記錄最大深度
        }
        v[cur].height = maxheight - dep; // 當前高度 = 子樹最大深度 - 當前深度
        return maxheight; // 回傳最大高度
    }
public:
    int root; // 根節點
    void update(int num, int val) {
        v[num].child.push_back(val); // 存取子節點
        v[val].parent = num; // 紀錄父節點
    }
    void find_root() { // 尋找根節點
        // 因為根節點不會有父節點
        // 所以找到 parent 為零的即為根節點
        for (int i = 1; i < v.size(); i++) {
            if (!v[i].parent) {
                root = i;
                break;
            }
        }
    }
    long long H() { // 計算高度總和
        dfs(root); // 從根節點開始深度優先搜尋(DFS)
        long long sum = 0;
        for (int i = 1; i < v.size(); i++) // 總和高度
            sum += v[i].height;
        return sum;
    }
    Tree(int n = 0): root(-1) {
        v.resize(n);
    }
};
int main() { _
    int N, K, tmp;
    cin >> N;
    Tree tree(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> K;
        while (K--) {
            cin >> tmp;
            tree.update(i, tmp);
        }
    }
    tree.find_root();
    cout << tree.root << endl;
    cout << tree.H() << endl;
}

$PYTHON$：

唯一一筆沒過的是：$RE \ (SIGSEGV)$，

錯誤訊息：記憶體區段錯誤！ $Segmentation \ fault (core dumped)$

根據討論區的說法，

那筆測資為一條鏈狀結構，

雖然已調整遞迴深度限制，

但 $PYTHON$ 仍無法使用這種方法 $AC$，

只能用 $Method \ 1.$。

$JUDGE\_RESULT$：$NA \ (score:95\%)$

from sys import stdin, setrecursionlimit
setrecursionlimit(200000)
class node:
    def __init__(self, parent = 0, height = 0):
        self.parent = parent # 父節點
        self.height =  # 高度
        self.child = [] # 子節點
class Tree:
    def __init__(self, n = 0):
        self.root = -1 # 根節點
        self.f = [node() for _ in range(n)] # 存取節點資料
    def dfs(self, cur, dep = 0):
        if not len(self.f[cur].child): # 為葉節點
            return dep # 回傳當前深度
        maxheight = 0 # 最大深度
        for i in self.f[cur].child: # 對每一個子節點遞迴
            tmp = self.dfs(i, dep + 1)
            maxheight = max(maxheight, tmp) # 記錄最大深度
        self.f[cur].height = maxheight - dep # 當前高度 = 子樹最大深度 - 當前深度
        return maxheight 回傳最大高度
    def update(self, num, val):
        self.f[num].child.append(val) # 存取子節點
        self.f[val].parent = num # 紀錄父節點
    def find_root(self): # 尋找根節點
        # 因為根節點不會有父節點
        # 所以找到 parent 為零的即為根節點
        for i in range(1, len(self.f)):
            if not self.f[i].parent:
                self.root = i
                break
    def H(self): # 計算高度總和
        self.dfs(self.root) # 從根節點開始深度優先搜尋(DFS)
        sum = 0
        for i in range(1, len(self.f)): # 總和高度
            sum += self.f[i].height
        return sum
N = int(stdin.readline().strip())
tree = Tree(N + 1)
for i in range(1, N + 1):
    data = [int(x) for x in stdin.readline().strip().split()]
    if len(data) == 1: continue
    for tmp in data[1:]:
        tree.update(i, tmp)
tree.find_root()
print(tree.root)
print(tree.H())

以上，
若有更好的想法歡迎提出哦！

搜尋此網誌

GT coding

[zerojudge] c463: apcs 樹狀圖分析 (Tree Analyses)

留言

張貼留言

熱門文章

[I/O 優化] PYTHON 篇

[TOI] 20200815 新手同好會－個人賽