模板

[TOC]

图论

连通性

强连通分量

void tarjan (int u) {
    dfn[u] = low[u] = ++tmp;
    st[++top] = u;
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan (v);
            low[u] = min (low[u], low[v]);
        } else if (!bel[v]) low[u] = min (low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        siz[++idx] = 1;
        bel[u] = idx;
        while (st[top] != u) {
            bel[st[top]] = idx;
            siz[idx]++;
            top--;
        }
        top--;
    }
}

缩点

for(int i = 1;i <= m; i ++) {
    if (bel[x[i]] != bel[y[i]]) {
        add (bel[x[i]], bel[y[i]], W[i]);
    }
}

点双

int low[M], dfn[M], st[M], top, tmp, idx;
vector<int> G[M], dc, dcc[M]; // dcc: 点双 dc：割点 G: 图
bool mark[M];// 是否为割点
void tarjan(int u, int root) {
	dfn[u] = low[u] = ++ tmp;
	st[++ top] = u;
	int chi = 0;
	for (auto v : G[u]) {
		if(!dfn[v]) {
			chi ++;
			tarjan(v, root);
			low[u] = min(low[u], low[v]);
			if((low[v] >= dfn[u] && u != root && !mark[u]) || (u == root && chi >= 2)) {
				mark[u] = 1;
				dc.push_back(u);
			}
			if(low[v] >= dfn[u]) {
				idx ++;
				do{
					int w = st[top --];
					dcc[idx].push_back(w);
				}while(st[top + 1] != v);
				dcc[idx].push_back(u);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

最短路

dijkstra

struct node {
    int dis, u;
    bool operator>(const node& a)const {
        return dis > a.dis;
    }
};
int dis[M];
priority_queue<node, vector<node>, greater<node> >q;
void Dijkstra(int s) {
    memset(dis, 0x3f3f3f3f, 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(int i = hd[u];i;i = e[i].nxt){
            int v = e[i].to,w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}

LCA

倍增

void dfs(int u, int f) {
    fa[u][0] = f, dep[u] = dep[f] + 1, vis[u] = 1;
    for (int i = 1; ; i ++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        ma[u][i] = min(ma[fa[u][i - 1]][i - 1] , ma[u][i - 1]);
        if (fa[u][i] == 0) {
            k = max(k, i - 1);
            break;
        }
    }
    for (auto v : g[u]) {
        if (v.to != f) {
            ma[v.to][0] = v.w;
            dfs(v.to, u);
        }
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    int x = u, y = v;
    int lu = INF, lv = INF;
    for (int i = k; i >= 0; i --){
        if(dep[fa[u][i]] >= dep[v])  lu = min(ma[u][i], lu), u = fa[u][i];
    }
    if(u == v) return min(lu, lv);
    for (int i = k; i >= 0; i --){
        if(fa[u][i] != fa[v][i]) lu = min(ma[u][i], lu), u = fa[u][i], lv = min(ma[v][i], lv), v = fa[v][i];
    }
    lu = min(ma[u][0], lu), lv = min(ma[v][0], lv);
    return min(lu, lv);
}

Tarjan

树链剖分

int dep[N], f[N], top[N], son[N], siz[N], hv[N];
void dfs1 (int u, int fa) {
	dep[u] = dep[fa] + 1, f[u] = fa, siz[u] = 1;
	for (auto v : G[u]) {
		if (v != fa) {
			dfs1 (v, u);
			siz[u] += siz[v];
			if (siz[son[u]] < siz[v]) son[u] = v;
		}
	}
	hv[son[u]] = 1;
}
void dfs2 (int u, int fa) {
	if (hv[u]) top[u] = top[fa];
	else top[u] = u;
	if (!son[u]) return;
	dfs2(son[u], u);
	for (auto v : G[u]) {
		if (v != son[u] && v != fa)
			dfs2(v, u);
	}
}
int lca (int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] > dep[top[v]]) u = f[top[u]];
		else v = f[top[v]];
	}
	return dep[u] < dep[v] ? u : v;
}

拓扑排序

数据结构

树状数组 - BIT

struct BIT {
    int c[N], maxn;
    #define l(x) x & -x
    void add (int x, int d) {for (int i = x; i <= maxn; i += l(i)) c[i] += d;}
    int sum (int x) {
        int res = 0;
        for (int i = x; i; i -= l(i)) res += c[i];
        return res;
    }
};

并查集 - DSU

struct DSU {
    int f[N], siz[N];
    void init () {
        for (int i = 1; i <= n; i ++) f[i] = i, siz[i] = 1;
    }
    int find (int x) {
        if(f[x] != x) f[x] = find(f[x]);
        return f[x];
    }
    void move (int x, int y) {
        x = find(x), y = find(y);
        if(siz[x] > siz[y]) swap(x, y); // 启发式合并
        if(x != y) {
            f[x] = y;
            siz[y] += siz[x];
            siz[x] = 0;
        }
    }
};