您的位置: 首页  >  IT文章  >  支配树

支配树

分类: IT文章 • 2022-05-07 08:52:56

支配树能够解决有向图必经点的问题。

定义，定理与约定

  • 默认有一个“源点” (s) 作为出发点。

  • 默认所有节点编号与其 (dfs) 序相同。

  • 定义 (u) “支配” (v) 表示如果想要经过 (v)，那么必须要经过 (u)。此时称 (u) 是 (v) 的“支配点”。

  • 由支配关系所组成的树成为支配树。

  • 众多定理...（待补）

DAG 的支配树的构造

外向树的支配树显然是其本身。

我们可以从 DAG 的源点开始，按照拓扑序遍历。当访问到一个点的时候，其最近支配点一定是其所有入边端点的支配树的 LCA（想走到 (u)，必须先走其入边端点）。

据此可以构建 DAG 的支配树。

相关题目：P2597 [ZJOI2012]灾难
； CF757F Team Rocket Rises Again

关键代码：

inline void tuopu() {
	que[++rear] = s;
	while (front < rear) {
		int cur = que[++front];
		int lca = 0;//Attention!!
		for (register unsigned int i = 0; i < iV[cur].size(); ++i) {
			int to = iV[cur][i];
			if (!lca)	lca = to;
			else	lca = get_lca(lca, to);//Attention!! : to
		}
		f[cur][0] = lca;
		for (register int i = 1; i <= 20; ++i)
			f[cur][i] = f[f[cur][i - 1]][i - 1];
		for (register unsigned int i = 0; i < V[cur].size(); ++i) {
			int to = V[cur][i];
			--d[to];
			if (!d[to])	que[++rear] = to;
		}
		dep[cur] = dep[f[cur][0]] + 1;
	}
}

普通有向图的支配树的构造

另一些定义及定理

  • 如果有 (u -> ... -> v)，且除了 (u, v)，其余 路径上的点 都满足其 (dfn) 大于 (dfn[v])，那么称 (dfs) 序最小的那个 (u) 为 (v) 的“半支配点”，标记为 (u = sdom[v])。

  • (sdom[u]) 一定是 (u) 的祖先，(sdom[1]=0) 除外。

证明：至少 (u) 的 dfs 树上父亲 (fa) 可以当作 (sdom[u])，因此子树不可能；如果 (sdom[u]) 在其它树上，那么至少能在树上找到一条路径 (anc -> sdom[u] -> u)，其中 (anc)（(u) 的祖先）会作为 (sdom[u])。

  • 保留树边，删除非树边，连接所有的 (sdom[cur] -> cur)，显然将形成一个 DAG，并且支配关系不变。

证明：不会

感性证明：我们站在 dfs 树为主体的角度看。显然 (sdom[cur]) 下面不会出现支配点，因为至少存在树上路径和 (sdom[cur] -> cur) 路径能够到达 (cur)。所以 (sdom[cur]) 下面的点到 (cur) 的非树边都可以删除。至于 (sdom[cur]) 的上面如果还有向 (cur) 的连边的话，那么为什么 (sdom[cur]) 不是那个祖先呢？

构造方法

需要构造出所有点的半支配点，然后删除原图边，半支配点向该点连边，转化为 DAG 上的问题。

如何构造半支配点？我们按编号从大到小枚举，对于每个点寻找反向边。首先如果对于当前节点 (v)，存在一个 (u -> v)，且 (u < v)，那么可以直接用 (u) 来更新 (sdom[v])；如果 (u -> v)，并且 (u > v)，那么 (u) 在之前一定已经遍历过了，那么根据定义我们沿着 (u) 到源点的链中已经遍历过的部分向上走，用路径上的 (sdom) 依次更新 (sdom[v])。这个过程可以用边带权并查集优化。

关键代码：

int sdom[N];
int fa[N], mn[N];
int find(int cur) {
	if (fa[cur] == cur)	return cur;//Attention!!!!!!!!!!!
	int faa = fa[cur];
	int anc = find(fa[cur]);
	MIN(mn[cur], mn[faa]);//Attnetion!!!!!
	fa[cur] = anc;
	return anc;
}
inline void get_sdom() {
	for (register int i = 1; i <= n; ++i)	fa[i] = mn[i] = sdom[i] = i;
	for (register int i = n; i > 1; --i) {
		int res = n;
		for (register unsigned int j = 0; j < iV[i].size(); ++j) {
			int to = iV[i][j];
			if (to < i)	MIN(res, to);
			else	find(to), MIN(res, mn[to]);//Attention!!!!
		}
		sdom[i] = res; fa[i] = dfa[i];
		MIN(mn[i], res);
	}
	sdom[1] = 0;
}

然后再建出 DAG 跑支配树即可。

模板

//P5180
int dfn[N], dcnt, mp[N], s;
int dfa[N];
void dfs_init(int cur) {
	dfn[cur] = ++dcnt;
	mp[dcnt] = cur;
	for (register int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to;
		if (!dfn[to])	dfs_init(to), dfa[dfn[to]] = dfn[cur];
	}
}

int sdom[N];
int fa[N], mn[N];
int find(int cur) {
	if (fa[cur] == cur)	return cur;//Attention!!!!!!!!!!!
	int faa = fa[cur];
	int anc = find(fa[cur]);
	MIN(mn[cur], mn[faa]);//Attnetion!!!!!
	fa[cur] = anc;
	return anc;
}
inline void get_sdom() {
	for (register int i = 1; i <= n; ++i)	fa[i] = mn[i] = sdom[i] = i;
	for (register int i = n; i > 1; --i) {
		int res = n;
		for (register unsigned int j = 0; j < iV[i].size(); ++j) {
			int to = iV[i][j];
			if (!dfn[to])	continue;
			if (to < i)	MIN(res, to);
			else	find(to), MIN(res, mn[to]);//Attention!!!!
		}
		sdom[i] = res; fa[i] = dfa[i];
		MIN(mn[i], res);
	}
	sdom[1] = 0;
}

int d[N];
int que[N], front, rear;
int f[N][21], dep[N];
inline int get_lca(int u, int v) {
	if (dep[u] < dep[v])	swap(u, v);
	for (register int i = 20; ~i; --i)
		if (dep[f[u][i]] >= dep[v])	u = f[u][i];
	if (u == v)	return u;
	for (register int i = 20; ~i; --i)
		if (f[u][i] != f[v][i])	u = f[u][i], v = f[v][i];
	return f[u][0];
}
inline void tuopu() {
	que[++rear] = s;
	dep[0] = -1;
	while (front < rear) {
		int cur = que[++front], lca = 0;
		for (register unsigned int i = 0; i < iV[cur].size(); ++i) {
			int to = iV[cur][i];
			if (!lca)	lca = to;
			else	lca = get_lca(lca, to);
		}
		f[cur][0] = lca; dep[cur] = dep[lca] + 1;//Attention!!!!!
		for (register int i = 1; i <= 20; ++i)
			f[cur][i] = f[f[cur][i - 1]][i - 1];
		for (register int i = head[cur]; i; i = e[i].nxt) {
			int to = e[i].to;
			--d[to];
			if (!d[to])	que[++rear] = to;
		}
	}
}

int siz[N];
void dfs_siz(int cur) {
	siz[cur] = 1;
	for (register int i= head[cur]; i; i = e[i].nxt) {
		int to = e[i].to;
		dfs_siz(to);
		siz[cur] += siz[to];
	}
}

inline void work() {
	memset(head, 0, sizeof(head));
	ecnt = 0;
	for (register int i = 2; i <= n; ++i)	addedge(f[i][0], i);
	dfs_siz(s);
}

int ans[N];
int main() {
	read(n), read(m);
	for (register int i = 1; i <= m; ++i) {
		int u, v; read(u), read(v);
		addedge(u, v);
	}
	dfs_init(1); s = dfn[1];
	
	for (register int i = 1; i <= n; ++i) {
		for (register int j = head[i]; j; j = e[j].nxt) {
			int to = e[j].to;
			aded(dfn[to], dfn[i]);
		}
	}
	memset(head, 0, sizeof(head));
	ecnt = 0;
	for (register int i = 1; i <= n; ++i) {
		for (register unsigned int j = 0; j < iV[i].size(); ++j) {
			int to = iV[i][j];
			addedge(to, i);
		}
	}
	
	get_sdom();
	
	memset(head, 0, sizeof(head));
	ecnt = 0;
	for (register int i = 1; i <= n; ++i)
		iV[i].clear();
	for (register int i = 2; i <= n; ++i)
		addedge(sdom[i], i), ++d[i], aded(i, sdom[i]),
		addedge(dfa[i], i), ++d[i], aded(i, dfa[i]);//Attention!!!!!!
	tuopu();
	work();
	for (register int i = 1; i <= n; ++i)
	 ans[mp[i]] = siz[i];
	for (register int i = 1; i <= n; ++i)
		printf("%d ", ans[i]);//Attention!!!!!!!!!!!!!!
	puts("");
	return 0;
}

/*
4 5
1 3
1 2
2 4
2 3
3 4
//4 1 1 1

10 15
1 2
2 3
3 4
3 5
3 6
4 7
7 8
7 9
7 10
5 6
6 8
7 8
4 1
3 6
5 3
//10 9 8 4 1 1 3 1 1 1

10 15
1 2
2 3
2 4
1 5
2 6
2 7
7 8
3 9
1 10
8 3
5 6
9 2
6 7
1 10
4 7
//10 2 2 1 1 1 2 1 1 1

21 36
1 2
1 3
1 4
2 5
5 6
3 7
7 8
6 9
4 10
3 11
7 12
2 13
1 14
13 15
1 16
12 17
7 18
14 19
6 20
11 21
14 16
11 17
18 4
18 18
11 19
9 11
15 1
21 8
2 15
15 14
2 18
16 2
14 14
13 12
4 19
19 20
//21 6 2 2 3 ...
*/

相关推荐