# 最小生成树

## Kruskal ($O(m \lg n)$)

void makeSet(int i) {
fa[i] = i;
}

int findSet(int i) {
if (i == fa[i]) return i;
else return fa[i] = findSet(fa[i]);
}

void unionSets(int i, int j) {
fa[findSet(i)] = findSet(j);
}

void kruskal() {
for (int i = 0; i < n; ++i) {
makeSet(i);
}
sort(edges.begin(), edges.end());
for (Edge e : edges) {
if (find_set(e.u) != findSet(e.v)) {
cost += e.weight;
result.push_back(e);
unionSets(e.u, e.v);
}
}
}

## Prim ($O(m \lg n)$)

void prim() {
for (int i = 0; i < n; ++i) {
int v = -1;
}
for (int j = 0; j < n; ++j) {
if (!vis[j] && (v == -1 || min_e[j].w < min_e[v].w)) {
v = j;
}
}

// if (min_e[v].w == INF) NO MST

vis[v] = true;
cost += min_e[v].w;
result.push_back({v, min_e[v].to});
for (int to = 0; to < n; ++to) {
if (adj[v][to] < min_e[to].w) {
min_e[to] = {adj[v][to], v};
}
}
}

# 单源最短路径

## Dijkstra (dense: $O(n^2+m)$)

void dijkstra() {
dis[s] = 0;
for (int i = 0; i < n; ++i) {
int v = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (v == -1 || dis[j] < dis[v])) {
v = j;
}
}

// if (dis[v] == INF)... FAILED
vis[v] = true;
for (Edge e : adj[v]) {
if (dis[v] + e.w < dis[e.to]) {
dis[e.to] = dis[v] + e.w;
prev[e.to] = v;
}
}
}
}

void print_path() {
vector<int> path;
for (int v = t; v != s; v = p[v]) {
path.push_back(v);
}
path.push_back(s);
reverse(path.begin(), path.end());
return path;
}

## Dijkstra (Sparse, set/priority_queue, $O(m \lg n)$)

void dijkstra() {
dis[s] = 0;
set<pair<int, int>> q; // or priority_queue here
q.insert({s, 0});
while (!q.empty()) {
int v = q.begin()->first;
q.erase(q.begin());

for (Edge e : adj[v]) {
if (dis[v] + e.w < dis[e.to]) {
q.erase({e.to, dis[e.to]});
dis[e.to] = dis[v] + e.w;
prev[e.to] = v;
q.insert({e.to, d[e.to]});
}
}
}
}

## Bellman-Ford

void bellman_ford() {
dis[s] = 0;
while (true) { // change to i:0 to n-1 avoid negative cycle.
bool any = false;
for (int j = 0; j < m; ++j) {
if (d[e[j].u] < INF) {
if (d[e[j].u] + e[j].w < d[e[j].v]) {
d[e[j].v] = d[e[j].u] + e[j].w;
prev[e[j].v] = e[j].u;
any = true;
}
}
if (!any) break;
}
}
}

## Floyd

void floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (d[i][k] < INF && d[k][j] < INF) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
//if (d[k][j] < INF && d[j][j] < 0 && d[j][i] < INF) {
//  d[k][i] = -INF; // negative circle
//}
}
}
}
}

# 强连通分量

## Kosaraju

void dfs1 (int v) {
vis[v] = true;
for (int i = 0; i < adj[v].size(); ++i) {
}
}
order.push_back(v);
}

void dfs2(int v) {
vis[v] = true;
component.push_back(v);
for (int i = 0; i < adj_rev[v].size(); ++i) {
}
}
}

void kosaraju() {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) {
if (!vis[i]) dfs1(i);
}
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) {
int v = order[n - 1 - i];
if (!vis[v]) {
dfs2(v);
// ... save the component
component.clear();
}
}
}

## Tarjan's SCC Algorithm

for (int i = 0; i < n; ++i) {
if (pre[i] == -1) tarjan(i);
}

void tarjan(int u) {
pre[u] = low[u] = t++;
s.push(u);
inStack[u] = true;
for (int j = 0; j < adj[u].size(); ++j) {
int v = adj[u][j];
if (pre[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], pre[v]);
}
}
if (pre[u] == low[u]) {
int v;
do {
v = s.top();
s.pop();
inStack[v] = false;
scc[v] = current_scc;
} while (u != v);
current_scc++;
}
}

## Tarjan 找割点/割边

-      if (low[v] >= pre[u] && u != 0) cut[v] = true;
+      if (low[v] >= pre[u] && u != 0) cut[u] = true;
void tarjan(int u) {
pre[u] = low[u] = t++;
for (int j = 0; j < adj[u].size(); ++j) {
int v = adj[u][j];
if (pre[v] == -1) {
if (u == 0 && j >= 1) cut[u] = true;

fa[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);

if (low[v] >= pre[u] && u != 0) cut[u] = true;
if (low[v] > pre[u]) bridge[u][v] = bridge[v][u] = true;
} else if (v != fa[u]) {
low[u] = min(low[u], pre[v]);
}
}
}

# 二分匹配

bool find (int u) {
rep (v, 1, m + 1) {
if (mp[u][v] && !vis[v]) {
vis[v] = true;
if (nex[v] < 0 || find(nex[v])) {
nex[v] = u; // reverse residual edge
return true;
}
}
}
return false;
}
int hungray() {
int ret = 0;
memset(nex, -1, sizeof(nex));
rep (u, 1, n + 1) {
memset(vis, 0, sizeof(vis));
if (find(u)) ret++;
}
return ret;
}

# 欧拉回路 ($O(n)$)

void euler() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
}
}

int first = 0;
while (!deg[first]) first++;

int v1 = -1, v2 = -1;
bool bad = false;

for (int i = 0; i < n; ++i) {
if (deg[i] & 1) {
if (v1 == -1) {
v1 = i;
} else if (v2 == -1) {
v2 = i;
} else {
}
}
}

if (v1 != -1) {
}

stack<int> st;
vector<int> res;
st.push(first);
while (!st.empty()) {
int v = st.top();
int i = 0;
for (int i = 0; i < n; ++i) {
}
if (i == n) {
res.push_back(v);
st.pop();
} else {
st.push(i);
}
}

if (v1 != -1) {
for (int i = 0; i < res.size(); ++i) {
if ((res[i] == v1 && res[i + 1] == v2) ||
(res[i] == v2 && res[i + 1] == v1)) {
vector<int> res2;
for (int j = i + 1; j < res.size(); ++j) {
res2.push_back(res[j]);
}
for (int j = 1; j <= i; ++j) {
res2.push_back(res[j]);
}
res = res2;
break;
}
}
}

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
}
}
cout << -1;
} else {
for (int x : res) cout << x << " ";
}
}

# 网络流

## Dinic ($O(V^2E)$)

class FlowEdge {
public:
int u, v;
int cap, flow = 0;
FlowEdge(int u, int v, int cap)
: u(u), v(v), cap(cap) {}
};

void addEdge(int u, int v, int cap) {
edges.push_back({u, v, cap});
edges.push_back({v, u, 0});
}

bool bfs() {
while (!q.empty()) {
int u = q.front();
q.pop();
for (int id : adj[u]) {
FlowEdge e = edges[id];
if (e.cap - e.flow < 1) continue;
if (level[e.v] != -1) continue;
level[e.v] = level[u] + 1;
q.push(e.v);
}
}
return level[t] != -1;
}

int dfs(int u, int pushed) {
if (!pushed) return 0;
if (u == t) return pushed;
for (int &cid = ptr[u]; cid < adj[u].size(); ++cid) {
int id = adj[u][cid];
FlowEdge e = edges[id];
int v = e.v;
if (level[v] != level[u] + 1 || e.cap - e.flow < 1) continue;

int delta = dfs(v, min(pushed, e.cap - e.flow));
if (!delta) continue;

edges[id].flow += delta;
edges[id ^ 1].flow -= delta;
return delta;
}
return 0;
}

int maxFlow() {
int ret = 0;
while (true) {
memset(level, -1, sizeof(level));
level[s] = 0;
q.push(s);

if (!bfs()) break;

memset(ptr, 0, sizeof(ptr));
while (true) {
int pushed = dfs(s, INF);
if (!pushed) break;
ret += pushed;
}
}
return ret;
}