---
# System prepended metadata

title: 實作面的小提醒

---

# 實作面的小提醒

[toc]

注意，本文假設了讀者了解這些資料結構。

所以如果你不了解這些資料結構，不妨就先了解這些資料結構。

## union find 的重要提醒

### No.1 要注意變數重名

#### 包裝成類

如果你用`struct`包裝成一個類的話，要注意，不能把聯集方法命名為`union`，因為這是C++的關鍵字。可以用`unite`(動詞)代替。

#### 不包裝成類

如果你打算把find, union等方法寫在外面，也要注意不能把find方法取名成`find`，因為這跟`<algorithm>`裡的`std::find`重名。
如果你要做union by rank，也不能把`rank`取成`rank`，因為這跟`<type_traits>`裡的`std::rank`重名。所以要不然加個下劃線什麼的。

所以用struct包裝起來可以省很多麻煩。

### No.2 要操作代表元

要操作代表元
要操作代表元
要操作代表元

十分重要！！！
以下面的[924. Minimize Malware Spread](https://leetcode.com/problems/minimize-malware-spread/description/?envType=problem-list-v2&envId=graph)之題解為例。

union find長這樣：
:::spoiler union find
```cpp=
struct UF {
    int root[301], rank[301], infcnt[301], cnt[301];
    UF(int n) {
        iota(root,root+n,0);
        fill(rank,rank+n,0);
        fill(infcnt,infcnt+n,0);
        fill(cnt,cnt+n,1);
    }
    void unite(int a,int b) {
        a = find(a), b = find(b);
        if (a!=b) {
            infcnt[a]=infcnt[b]=infcnt[a]+infcnt[b];
            cnt[a]=cnt[b]=cnt[a]+cnt[b];

            if (rank[a]<rank[b]) {
                root[a]=b;
            }
            else {
                root[b]=a;
                if (rank[a]==rank[b]) rank[a]++;
            }
        }
    }
    int find(int a) {
        if (root[a]==a) return a;
        return root[a]=find(root[a]);
    }
};
```
:::

Solution class是
:::spoiler Solution
```cpp=
class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        UF uf(n);
        for (int i : initial) uf.infcnt[i]++;

        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                if (graph[i][j]) {
                    uf.unite(i,j);
                }
            }
        }

        sort(initial.begin(),initial.end());
        int deccnt = 0;
        int ans = initial[0];
        for (int i : initial) {
            int fi = uf.find(i);
            if (uf.infcnt[fi]==1) {
                if (uf.cnt[fi]>deccnt) {  
                    ans = i;
                    deccnt = uf.cnt[fi];
                }
            }
        }
        return ans;
    }
};
```
:::

所謂“總是操作代表元”說的就是，不要把
```cpp=
int fi = uf.find(i);
if (uf.infcnt[fi]==1) {
    if (uf.cnt[fi]>deccnt) {  
        ans = i;
        deccnt = uf.cnt[fi];
    }
}
```
寫成
```cpp=
if (uf.infcnt[i]==1) {
    if (uf.cnt[i]>deccnt) {  
        ans = i;
        deccnt = uf.cnt[i];
    }
}
```
不然你就會莫名其妙的少掉30分鐘時間debug

可別小看這個錯誤，尤其是在你很熟練union find的寫法後，有些進階的題目會要求你紀錄每個集團的邊數，點數，最小最大點等等。記錄這些既然簡單，難就難在一不小心就又寫成以i做索引。所以

>要操作代表元
要操作代表元
要操作代表元

### No.3 沒有必要union by `rank`

如果懶得寫，也可以寫一個randomized union了事，或甚至直接不寫。
因為path compression已經足夠了。
而path compression一定要寫，不然會變成$O(n\log n)$

## Dijkstra/BFS最短路的重要提醒

### using INFO

在多層圖中，有時會有很多狀態，得用`tuple<很多元素>`
這時候比起
```cpp
priority<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> pq;
```

不如
```cpp
using INFO = tuple<int,int,int,int>;
priority<INFO,vector<INFO>,greater<INFO>> pq;
```

### 優化

就bfs而言，只要用`bool been`就可以保證優化

就dijstra而言，要用
```cpp
ll been[N];
memset(been,0x3f,sizeof(been));
```

而且，還需要這兩個優化，不然會超時。
```cpp=
while (!pq.empty()) {
    auto [dist,node] = pq.top();
    pq.pop();
    
    if (dist > been[node]) continue; // opti 1
    for (auto [next,weight] : G[node]) {
        ll ndist = dist + weight;
        if (ndist >= been[next]) continue;// opti 2
        been[next] = ndist;
        pq.emplace(next,ll);
    }
}
```
這兩個優化不影響正確性，而極大的影響速度。
對於優化一，不能改寫成
`if (dist != been[node]) continue;`

比方說，就[1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/description/)而言，你需要把

```cpp=
int dir[] = {0,1,0,-1,0};
using da = tuple<int,int,int>;
class Solution {
public:
    vector<vector<int>> hei;
    vector<vector<int>> been;
    int n,m;
    int unvis = 1e8;
    int dijkstra() {
        been.assign(n,vector<int>(m,unvis));
        priority_queue<da,vector<da>,greater<da>> que;
        que.emplace(0,0,0);
        been[0][0] = true;
        while (!que.empty()) {
            auto [dcurr,i,j] = que.top();
            que.pop();
            if (dcurr > been[i][j]) continue; // 這一行改成>=才能ＡＣ
            if (i == n-1 && j == m-1) return dcurr;

            for (int d=0;d<4;d++) {
                int inext = i + dir[d], jnext = j + dir[d+1];
                if (inext == -1 || inext == n || jnext == -1 || jnext == m)
                    continue;
                int dnext = max(abs(hei[inext][jnext]-hei[i][j]),dcurr);
                if (dnext >= been[inext][jnext]) continue;
                been[inext][jnext] = dnext;
                que.emplace(dnext,inext,jnext);
            }
        }
        return been[n-1][m-1];
    }
    int minimumEffortPath(vector<vector<int>>& hei) {
        n = hei.size();
        m = hei[0].size();
        this->hei = hei;
        return dijkstra();
    }
};
```

但是，對於典型的Dijkstra，卻可以用`!=`，很奇妙。 >_<

## 實作鏈式前向星的重要提醒

### 初始化

每次開始建圖前，都要記得初始化`cnt=0`還要`memset(head,-1,sizeof(head))`
不然容易陷入無窮迴圈。

這還算是一個好抓的bug，但是下面這一個

### 無向圖建圖開二倍空間

知道的人都知道，對於無向圖，每次要連接`u`, `v`時，
要call兩次加邊程式：
```cpp!
add_edge(u,v);
add_edge(v,u);
```

這是因為鏈式前向星本質上是為有向圖服務的。

但是不知道的人就不知道，在這種情況下，你的`edges`要開
題目給出的兩倍空間，因為每一個無向邊都 corresponds to 兩個有向邊。

千萬要注意！！！否則就會：
![image](https://hackmd.io/_uploads/BJRglg29gx.png)


經驗告訴我，這是最容易被忘記的注意事項，而且一但忘記了也很危險。因為sample case給出的邊數都不會大，就更難抓出這種讀取越界的問題了。

## dp

dp 有分刷表法跟填表法。
刷表法就是用已知狀態填未知狀態；填表法(or 查表法)就是從未知狀態去看他 depend on 哪些狀態。
比方說 Bellman-Ford 是一種刷表法。
要挑適合的。大多時候都是用填表法，但不要忘記刷表法的存在。
比方說如果在 https://leetcode.cn/problems/find-x-value-of-array-i/solutions/3656580/zi-shu-zu-dp-shua-biao-fa-pythonjavacgo-8lonk/ 用填表法，就是 $O(nk^2)$ 反之就能有 $O(nk)$ 