---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework10 (quiz10)
contributed by < `RinHizakura` >

> [第 10 週測驗題](https://hackmd.io/@sysprog/2020-quiz10)
> [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz10)
## 測驗 `1`

## 測驗 `2`

逐行釐程式原理。

int *countSubgraphsForEachDiameter(int n,
                                   int **edges,
                                   int edgesSz,
                                   int *edges0sz,
                                   int *rsz)
{
    uint8_t d[n][n]; /* distance */
    memset(d, 0xFF, sizeof(d));
    uint16_t conn[n];
    ITERATE (i, 0, n)
        conn[i] = 1 << i;

   

* 維護二維的陣列 `d`，`d` 用來紀錄兩點間的最短距離，因此首先由 memset 初始化成 8 bits 可表示的最大距離 0xFF
* 因為限制點最多 15 個，因此 8 bit 已經足以表示彼此的距離
* 維護陣列 `conn` bitmask，`conn[u]` 中的 bit 為 1 的位置表示點 u 可以直接到達(不需要經過其他)的點

    for (int z = 0; z < edgesSz; z++) {
        int *e = edges[z];
        int u = e[0] - 1, v = e[1] - 1;
        d[u][v] = d[v][u] = 1;
        conn[u] |= 1 << v, conn[v] |= 1 << u;
    }
    
    ITERATE (k, 0, n)
        ITERATE (i, 0, n)
            ITERATE (j, 0, n)
                d[i][j] = MIN(d[i][j], d[i][k] + d[k][j]);
    int *rv = calloc(n - 1, sizeof(int));

* 則 for 迴圈中首先計算這些可以直接到達的點的距離和 bitmask
* 往後的 3 個 `ITERATE` 形成的迴圈中，計算每個點間接到達其他點的最短距離
* 類似 [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) 的應用，只是在本題中 edge 的長度皆為 1，所以又更單純一些
* 接著配置回傳的空間 `rv`

     ITERATE (S, 1, (1 << n)) {
        int ctmp = 1 << __builtin_ctz(S);
        while (1) {
            int conn_nxt = ctmp;
            ITERATE (d, 0, n)
                if ((ctmp >> d) & 1)
                    conn_nxt |= conn[d];
            conn_nxt &= S;
            if (COND1)
                break;
            ctmp = conn_nxt;
        }
        if (COND2)
            continue;
        uint8_t ret = 0;
        ITERATE (i, 0, n)
            if ((S >> i) & 1)
                ITERATE (j, 0, i)
                    if (((S >> j) & 1) && (ret < d[i][j]))
                        ret = d[i][j];
        if (!ret)
            continue;
        rv[ITER]++;
    }

* 則可以窮舉所有 subset `S` 下最長距離，就可以有多少 subset 下的 max distance 為 1 到 (n - 1)
* 首先，要判斷此 subset 是否為 conneted，這裡使用 BFS 來判斷
* 27 行的 `ctmp` 透過 `__builtin_ctz` 取出 S 中的第一個點為起點
* 28 行的迴圈中，根據第 30 行的 `ITERATE` 不斷把可以連接到的點加入，判斷基於目前 `ctmp` 的點，可以再找到其他的哪些點
* 33 行的 `conn_nxt &= S` 確保只考慮存在目標 subset `S` 中的點
* 因此 `ctmp` 會不斷被更新，直到此次的狀態與前一次的相同，也就是 BFS 無法再往下找到新的結果，因此 `COND1 = (a) conn_nxt == ctmp`
* BFS 結束後，判斷這些點是否包含 subset 中的所有點，如果不包含，則不為滿足題意的 tree，做 continue
* 所以對應的操作是 `COND2 = (e) ctmp ^ S`
* 如果滿足，則去判斷此 connected graph 的最大直徑，在 41 行中簡單的直接搜尋 subset 中兩點距離的最大值
* 最後則根據此最大距離去 index `rv`，注意到 rv 儲存的是 (1 到 n - 1) 長度的組合數，所以 `ITER = (d) --ret`

在 leetcode 上執行並且正確的結果