## C++

https://cp.wiwiho.me/lessons/
https://oi-wiki.org/
https://www.techiedelight.com/zh-tw/determine-if-a-string-is-numeric-in-cpp/
https://github.com/brianbbsu/8BQube

### 加速

ios_base::sync_with_stdio(0);
cin.tie(0);

### vector

#include <vector>

vector<int> v(10, 0); // 宣告一個大小為 10, 全為 0 的 vector

v.push_back(1); // 在 vector 最後面新增一個元素 1
v.pop_back(); // 一次只能從尾端移除一個元素，不能指定移除的數量

v.size(); // 取得目前 vector 裡的元素個數
v.capaciy(); // 取得目前 vector 裡的預先配置的空間大小
v.reserve(5); // 預留 5 個空間
v.shrink_to_fit(); // 釋放（free）那些尚未使用的空間
v.resize(5); // resize 變大時會把多的元素補 0
v.resize(5, 10); // 順便指定初始值為 10

reverse(v.begin(), v.end()); // 將 vector 顛倒

v.erase(v.begin() + 2); // 刪除第三個元素
v.erase(v.begin(), v.begin() + 3); // 刪除前 3 個元素

#### sort()

#include <algorithm>

// 自訂排序
bool cmp(const int a, const int b) {
  return a < b; // 由大到小排序，a 是第二個元素, b 是第一個元素。
}


vector<int> v = {2, 4, 5, 3, 1, 6, 7};
sort(v.begin(), v.end()); // 從小到大排序

sort(v.begin(), v.end(), cmp);

### stack

#include <stack>

stack<int> s;
s.push(1);

// 用 vector 建構 stack
vector<int> v = {1, 2, 3};
stack<int, vector<int>> s(v);

// 也可以用 deque
deque<int> dq = {1, 2, 3};
stack<int, deque<int>> s(dq);

s.pop(); // 從頂端移除元素
s.empty(); // 判斷是否為空
s.size(); // 判斷元素數量
s.top(); // 查看頂端元素

### deque

deque 是一個雙向佇列(double-ended queue)，在頭尾兩端插入及刪除十分快速

#include <deque>

deque<int> dq = {1, 2, 3, 4}; 

dq.push_back(5); // [1, 2, 3, 4, 5]
dq.pop_front(); // [2, 3, 4, 5]
dq.push_front(0); // [0, 2, 3, 4, 5]
dq.pop_back(); // [0, 2, 3, 4] 

### queue

#include <queue>

queue<int> q;
q.push(1); // 在尾部加入元素
q.pop(); // 取出頭部元素，會將元素從 queue 中移除
q.front(); // 取得頭部元素，不會將元素移除
q.back(); // 取得尾巴元素
q.size();
q.empty();
q.clear(); // 清空 queue;

### map

#include <map>

map<int, string> mp = {
  {0, "Tom"}
};
mp[1] = "Alen";
mp.insert(pair<int, string>(2, "John"));

// 遍歷 map 會發現 key 由小到大排序
for (auto m : mp) {
  cout << mp.first << " -> " << mp.second;
}

mp.erase(1); // 刪除元素

// 判斷元素是否存在
// count() 存在回傳 1, 不存在回傳 0
int cnt = mp.count(1);

// find() 找到元素會回傳 iterator, 否則回傳 end() iterator
auto it = mp.find(1);

### set

set 容器裡面的元素是**唯一的**，具有**不重複**的特性，而且是**有排序的**容器， set 容器裡面**元素的值是不可修改**，但 set 容器**可以插入或刪除元素**

#include <set>

// 初始化
set<int> st{1, 2, 3, 4, 5};

// 用 array 初始化
int arr[] = {1, 2, 3, 4, 5};
set<int> st(arr, arr + 5);

st.insert(6); // 加入元素
st.erase(5); // 刪除指定元素
st.clear(); // 清空 set
st.empty();

// 只能迴圈遍歷元素
for (auto it=st.begin(); it!=st.end(); it++) cout << *it << " ";

// 判斷元素是否存在
// count() 存在回傳 1, 不存在回傳 0
st.count(4);

// find() 找到元素會回傳 iterator, 否則回傳 end() iterator
auto search = st.find(4);
if (search != st.end()) cout << "found " << *search;

### String

### pair

#include <pair>

pair<int, string> p;
pair<int, string> p(1, "Tom");

### find()

#include <algorithm>

int arr[] = {1, 2, 3, 4, 5, 6};
*p = find(arr, arr+5, 3); // find 3
if (p == arr + 5) cout << "not found\n";
else cout << "found: " << *p << endl;

vector<int> v = {1, 2, 3, 4, 5, 6};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
if (it != v.end()) 
  cout << "found " << *it << ", index: " << distance(v.begin(), it) << endl; 

#### find_if()

#include <algorithm>

template<typename T>
bool equal_5(T val) {
  return val == 5;
}

vector<int> v = {1, 2, 3, 4, 5, 6};
vector<int>::iterator it = find_if(v.begin(), v.end(), equal_5<int>);
if (it != v.end()) cout << "found\n";

### 判斷字母數字

#include <ctype.h>

if (isalpha('a')) cout << "alpha\n";

## Java

## 圖的儲存

### 鄰接矩陣

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool>> adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int v = 1; v <= n; ++v) {
        if (adj[u][v]) {
          dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;
    vis.resize(n + 1, false);
    adj.resize(n + 1, vector<bool>(n + 1, false));

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;
    }

    return 0;
}

### 鄰接表

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<int>> adj;  // adj[u] 儲存與 u 相鄰的節點

bool find_edge(int u, int v) {
    for (int i = 0; i < adj[u].size(); ++i)
        if (adj[u][i] == v)
            return true;
    return false;
}

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

int main() {
    cin >> n >> m;
    vis.resize(n + 1, false);
    adj.resize(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    return 0;
}

## 質數

### 質數檢測

bool millerRabin(int n) {
  if (n < 3 || n % 2 == 0) return n == 2;
  int u = n - 1, t = 0;
  while (u % 2 == 0) u /= 2, ++t;
  // test_time 為測試次數，建議設為不小於 8
  // 的整數以確保正確率，但也不宜過大，否則會影響效率
  for (int i = 0; i < test_time; ++i) {
    int a = rand() % (n - 2) + 2, v = quickPow(a, u, n);
    if (v == 1) continue;
    int s;
    for (s = 0; s < t; ++s) {
      if (v == n - 1) break;  // 得到平凡平方根 n-1，通過此輪測試
      v = (long long)v * v % n;
    }
    if (s == t) return 0;
  }
  return 1;
}

### 質數篩選

void init(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) pri[cnt++] = i;
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] > n) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // i % pri[j] == 0，換言之，i 之前被 pri[j] 篩過了
        // 由於 pri 裡面質數是從小到大的，所以 i乘上其他的質數的結果一定會被
        // pri[j]的倍數篩掉，就不需要在這裡先篩一次，所以這裡直接 break
        break;
      }
    }
  }
}

## MST

### Prim's Algorithm

- 以 **vertex** 為主要考量
- 適合用在稠密圖
- edge 很多時，較 Kruskal 有效率
- 演算法 (N = number of vetex)
- 建一個存 edges 的 priority queue，權重小的優先
- 見一個 bool arr，存哪些點已經加入樹中
- 從任意的點當作起點，不斷執行下列演算法，直到產生 N-1 個 edges
- 若選中的節點已在樹中，跳過本次
- 將目前節點標示為已加入
- PQ 加入和目前節點相鄰的所有 edges
- 從 PQ 中拿出一個 edge，並移動到下個節點

class MST {
    static class Edge {
        public int v, t, w;

        public Edge(int _v, int _t, int _w) {
            v = _v;
            t = _t;
            w = _w;
        }
    }

    static ArrayList<Edge> prim(int[][] g) {
        int n = g.length, m = 0;
        PriorityQueue<Edge> edges = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(MST.Edge e1, MST.Edge e2) {
                return e1.w - e2.w;
            }
        });

        int v = 0;
        boolean[] contains = new boolean[n];
        ArrayList<Edge> mst = new ArrayList<>();
        while (m < n) {
            if (contains[v])
                continue;
            contains[v] = true;

            for (int t = 0; t < n; t++) {
                if (g[v][t] != 0) {
                    if (!contains[t])
                        edges.add(new Edge(v, t, g[v][t]));
                }
            }

            Edge next = edges.poll();
            mst.add(next);
            v = next.t;
            m++;
        }

        return mst;
    }
}

### Kruskal's algorithm

- 以 edge 為主的演算法
- 適合稀疏圖 (點很多，但是邊不多)
- 因為要先求出所有邊並排序，圖有很多 edge 時很不適合
- 演算法
- 建一個 array 存所有 edges，並 sort
- 從第一個 edge 開始向後看，執行以下演算法，直到產生 N-1 個 edge
- 拿出目前最小的 edge，並檢查加入此 edge 是否形成 cycle，若會 cycle 則跳過
- 若兩個點都已經在 MST 中，會產生 cycle
- 將 edge 加入 MST，並進行下一次演算法

import java.util.*;

class MST {
    static class Edge {
        public int v, t, w;

        public Edge(int _v, int _t, int _w) {
            v = _v;
            t = _t;
            w = _w;
        }
    }

    static ArrayList<Edge> kruskal(int[][] g) {
        int n = g.length, m = 0;
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // init j=i+1 避免重複的 edge
            for (int j = i + 1; j < n; j++) {
                if (g[i][j] == 0)
                    continue;
                edges.add(new Edge(i, j, g[i][j]));
            }
        }
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(MST.Edge e1, MST.Edge e2) {
                return e1.w - e2.w;
            }

        });

        boolean[] contains = new boolean[n];
        ArrayList<Edge> mst = new ArrayList<>();
        for (int i = 0; i < edges.size() && m < n; i++) {
            Edge edge = edges.get(i);
            if (contains[edge.v] && contains[edge.t])
                continue;
            mst.add(edge);
            m++;
        }

        return mst;
    }
}

## Shortest Path

### All Pair

Floyd：適用於任何圖，但必須存在最短路徑。

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k]+f[k][y])
    }
  }
}

Bellman–Ford：可求負權重的圖，並判斷是否存在最短路徑。

鬆弛操作（經過新的中繼點）對應公式：$dis(v) = \min(dis(v), dis(u) + w(u, v))$

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  bool flag;  // 判斷一輪循環過程中是否發生鬆弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int u = 1; u <= n; u++) {
      if (dis[u] == inf) continue;
      // 無窮大與常數加減仍為無窮大
      // 因此最短路長度為 inf 的點引出的邊不可能發生鬆弛操作
      for (auto ed : e[u]) {
        int v = ed.v, w = ed.w;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          flag = true;
        }
      }
    }
    // 沒有可以鬆弛的邊時就停止
    if (!flag) break;
  }
  // 第 n 輪循環仍可鬆弛時說明 s 點可以抵達負環
  return flag;
}

### Single-Source

Dijkstra：求**非負權重**單源最短路徑。

// 使用 priority_queue 實現
struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}