NOIp 图论算法专题总结 (2)

系列索引：

NOIp 图论算法专题总结 (1)

NOIp 图论算法专题总结 (2)

NOIp 图论算法专题总结 (3)

树链剖分

https://oi-wiki.org/graph/heavy-light-decomposition/

qRange：将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(val\)
updRange：求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和
qSon：将以 \(x\) 为根节点的子树内所有节点值都加上 \(val\)
updSon：求以 \(x\) 为根节点的子树内所有节点值之和

时间复杂度 \(O(n\log^2n)\)。

int w[N], wt[N];

int t[N<<2], laz[N<<2];

int son[N], id[N], fa[N], dep[N], siz[N], top[N];

inline void pushdown(int k, int len) {

	laz[k<<1]+=laz[k];

	laz[k<<1|1]+=laz[k];

	t[k<<1] = (t[k<<1] + laz[k]*(len-(len>>1))) % MOD;

	t[k<<1|1] = (t[k<<1|1] + laz[k]*(len>>1)) % MOD;

	laz[k]=0;

}

void build(int k, int l, int r) {

	if (l==r) {t[k] = wt[l] % MOD; return; }

	int mid=(l+r)>>1;

	build(k<<1, l, mid);

	build(k<<1|1, mid+1, r);

	t[k] = (t[k<<1] + t[k<<1|1]) % MOD;

}

int query(int k, int l, int r, int x, int y) {

	if (x<=l && r<=y) {return t[k]; }

	if (laz[k]) pushdown(k, r-l+1);

	int mid=(l+r)>>1, res=0;

	if (x<=mid) res = (res + query(k<<1, l, mid, x, y)) % MOD;

	if (y>mid) res = (res + query(k<<1|1, mid+1, r, x, y)) % MOD;

	return res;

}

void update(int k, int l, int r, int x, int y, int val) {

	if (x<=l && r<=y) {laz[k]+=val, t[k]+=val*(r-l+1); return; }

	if (laz[k]) pushdown(k, r-l+1);

	int mid=(l+r)>>1;

	if (x<=mid) update(k<<1, l, mid, x, y, val);

	if (y>mid) update(k<<1|1, mid+1, r, x, y, val);

	t[k] = (t[k<<1] + t[k<<1|1]) % MOD;

}

inline int qRange(int x, int y) {

	int ans=0;

	while (top[x]!=top[y]) {

		if (dep[top[x]] < dep[top[y]]) swap(x, y);

		ans = (ans + query(1, 1, n, id[top[x]], id[x])) % MOD;

		x=fa[top[x]];

	}

	if (dep[x]>dep[y]) swap(x, y);

	ans = (ans + query(1, 1, n, id[x], id[y])) % MOD;

	return ans;

}

inline void updRange(int x, int y, int val) {

	val %= MOD;

	while (top[x]!=top[y]) {

		if (dep[top[x]] < dep[top[y]]) swap(x, y);

		update(1, 1, n, id[top[x]], id[x], val);

		x=fa[top[x]];

	}

	if (dep[x]>dep[y]) swap(x, y);

	update(1, 1, n, id[x], id[y], val);

}

inline int qSon(int x) {

	return query(1, 1, n, id[x], id[x]+siz[x]-1);

}

inline void updSon(int x, int val) {

	update(1, 1, n, id[x], id[x]+siz[x]-1, val);

}

void dfs1(int x, int f, int d) {

	dep[x] = d, fa[x] = f, siz[x] = 1;

	int heavy=-1;

	for (rint i=head[x]; i; i=nex[i]) {

		int &y=to[i]; if (y==f) continue;

		dfs1(y, x, d+1);

		siz[x]+=siz[y];

		if (siz[y]>heavy) son[x]=y, heavy=siz[y];

	}

}

void dfs2(int x, int tp) {

	id[x]=++id[0], wt[id[0]]=w[x], top[x]=tp;

	if (!son[x]) return;

	dfs2(son[x], tp);  // heavy son first

	for (rint i=head[x]; i; i=nex[i]) {

		int &y=to[i]; if (y==fa[x] || y==son[x]) continue;

		dfs2(y, y); // light son with new chain

	}

}

dfs1(root, 0, 1);

dfs2(root, root);

build(1, 1, n);

求树的重心

https://oi-wiki.org/graph/tree-misc/

拓扑排序

在顶点活动网 (Activity On Vertex network, AOV) 中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列 (Topological order)，由 AOV 网构造拓扑序列的过程叫做拓扑排序 (Topological sort)。AOV 网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

Kahn 算法：

将入度为 0 的边组成一个集合 \(S\)，每次从 \(S\) 里面取出一个顶点 \(v\) (可以随便取) 放入 \(L\)，然后遍历顶点 \(v\) 的所有边 \((u_1, v), (u_2, v), (u_3, v) \cdots\) 并删除，判断如果该边的另一个顶点在移除这一条边后入度为 0，那么就将这个顶点放入集合 \(L\) 中。

不断地重复取出顶点。

最后当集合为空后，就检查图中是否存在任何边。如果有，那么这个图一定有环路，否则返回 \(L\)，\(L\) 中顺序就是拓扑排序的结果。

常用队列实现 \(S\) 集合。时间复杂度 \(O(V+E )\)。

int ind[N], topo[N], cnt;

queue<int> q;

for (int i=1, a, b; i<=m; i++)

    scanf("%d%d", &a, &b), add(a, b), ++ind[b];

for (int i=1; i<=n; i++) if (!ind[i]) q.push(i);

while (!q.empty()) {

    int t = q.top(), q.pop(); topo[++cnt] = t;

    for (int i=head[t]; i; i=nex[i]) {

        --ind[to[i]];

        if (!ind[to[i]]) q.push(to[i]);

    }

}

if (cnt < n) printf("有环！")

强连通分量

在一个有向图中，如果某两点间都有互相到达的路径，那么称中两个点强连通，如果任意两点都强连通，那么称这个图为强连通图；一个有向图的极大强连通子图称为强连通分量。

一个强连通分量中的点一定处于搜索树中同一棵子树中。

Tarjan 算法：

low[] 表示这个点以及其子孙节点连的所有点中dfn最小的值.
s[] 表示当前所有可能能构成是强连通分量的点.
col[] 对强连通分量进行染色.
v[to[k]]==false 说明无论如何这个点也不能与u构成强连通分量，因为它不能到达u.
low[x]==dfn[x] 说明u点及u点之下的所有子节点没有边是指向u的祖先的了，即u点与它的子孙节点构成了一个最大的强连通图即强连通分量.
if (!dfn[i]) tarjan(i); Tarjan一遍不能搜完所有的点，因为存在孤立点. 所以我们要对一趟跑下来还没有被访问到的点继续跑Tarjan.

均摊时间复杂度 \(O(n)\).

int dfn[N], low[N], t, s[N], st;

int col[N], ct;

bool v[N];

void tarjan(int x) {

    dfn[x]=low[x]=++t, s[++st]=x, v[x]=true;

    for (int k=head[x]; k; k=nex[k]) {

        if (dfn[to[k]]) {if (v[to[k]]) low[x]=min(low[x], dfn[to[k]]); }

        else tarjan(to[k]), low[x]=min(low[x], low[to[k]]);

    }

    if (low[x]==dfn[x]) {

        col[x]=++ct, v[x]=false;

        while (s[st]!=x) col[s[st]]=ct, v[s[st--]]=false;

        --st;

    }

}

for (int i=1; i<=n; ++i) if (!dfn[i]) tarjan(i);

[USACO06JAN] The Cow Prom:

for (rint i=1; i<=n; ++i) ++cnt[col[i]];

for (rint i=1; i<=ct; ++i) if (cnt[i]>1) ++ans;

printf("%d\n", ans);

缩点

缩点: 对于 贡献具有传递性 的题，因为强连通分量中的每两个点都是强连通的，可以将一个强连通分量当做一个 超级点，而点权按题意来定.

POJ2186 Popular Cows: 告诉你有n头牛，m个崇拜关系，并且崇拜具有传递性，如果a崇拜b，b崇拜c，则a崇拜c，求最后有几头牛被所有牛崇拜.

显然一个强联通分量内的所有点都是满足条件的，我们可以对整张图进行缩点，然后就简单了.

剩下的所有点都不是强连通的，现在整张图就是一个DAG（有向无环图）.

那么就变成一道水题了，因为这是一个有向无环图，不存在所有点的出度都不为零的情况.

所以必然有1个及以上的点出度为零，如果有两个点出度为零，那么这两个点肯定是不相连的，即这两圈牛不是互相崇拜的，于是此时答案为零，如果有1个点出度为0，那么这个点就是被全体牛崇拜的.

这个点可能是一个强联通分量缩成的 超级点，所以应该输出整个强联通分量中点的个数.

— stxy-ferryman

/* 以上同 Tarjan 求强连通分量. */

int deg[N], cnt[N];

int tot=0, ans=0;

for (int i=1; i<=n; ++i) {

    for (int k=head[i]; k; k=nex[k]) if (col[to[k]]!=col[i]) ++deg[col[i]];

    ++cnt[col[i]];

}

for (int i=1; i<=ct; ++i) if (!deg[i]) ++tot, ans=cnt[i];

if (!tot || tot>1) printf("0\n"); else printf("%d\n", ans);

割点、桥

无向图.

割点

特判：根节点如果有两个及以上的儿子，那么他也是割点.

int dfn[N], low[N], t, root;

bool cut[N];

void tarjan(int x) {

    int flag=0;

    dfn[x]=low[x]=++t;

    for (int k=head[x]; k; k=nex[k]) {

        if (dfn[to[k]]) low[x]=min(low[x], dfn[to[k]]);

        else {

            tarjan(to[k]), low[x]=min(low[x], low[to[k]]);

            if (low[y]>=dfn[x]) {

                ++flag;

                if (x!=root || flag>1) cut[x]=true;

            }

        }

    }

}

for (int i=1; i<=n; ++i) if (!dfn[i]) tarjan(root=i);

for (int i=1; i<=n; ++i) if (cut[i]) printf("%d ", i);

桥

邻接表存图编号从2开始. 即开头 head[0]=1;.

int dfn[N], low[N], t;

bool bdg[N<<1];

void tarjan(int x, int last) {

    dfn[x]=low[x]=++t;

    for (int k=head[x]; k; k=nex[k]) {

        if (dfn[to[k]]) if (i!=(last^1)) low[x]=min(low[x], dfn[to[k]]);

        else {

            tarjan(to[k], k), low[x]=min(low[x], low[to[k]]);

            if (low[y]>=dfn[x]) bdg[k]=bdg[k^1]=true;

        }

    }

}

for (int i=1; i<=n; ++i) if (!dfn[i]) tarjan(i, 0);

for (int i=2; i<head[0]; i+=2) if (bdg[i]) printf("%d %d\n", to[i^1], to[i]);

杂项

图论技巧

巴特西