连通性问题 强连通分量(SCC)
1. 缩点
当一个图中出现一个环时,可以缩成一个点。
【模板】缩点
题目描述
给定一个 n n n 个点 m m m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。
输入格式
第一行两个正整数 n , m n,m n,m
第二行 n n n 个整数,其中第 i i i 个数 a i a_i ai 表示点 i i i 的点权。
第三至 m + 2 m+2 m+2 行,每行两个整数 u , v u,v u,v,表示一条 u → v u\rightarrow v u→v 的有向边。
输出格式
共一行,最大的点权之和。
样例 #1
样例输入 #1
2 2 1 1 1 2 2 1
样例输出 #1
2
提示
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 4 1\le n \le 10^4 1≤n≤104, 1 ≤ m ≤ 1 0 5 1\le m \le 10^5 1≤m≤105, 0 ≤ a i ≤ 1 0 3 0\le a_i\le 10^3 0≤ai≤103。
来自洛谷 P3387 【模板】缩点
dfn 记录树遍历到的节点的计数标识,low 记录当前节点的祖先节点。
栈中存树,成环时取出。
然后重新建图,通过拓扑排序求从入度为 0 的点到出度为 0 的点的经过中,每个点可以获得的最大点权和。
由此得解。
void tarjan(int x)
{
dfn[x] = low[x] = ++step;
stk.push(x);
ins[x] = 1;
for (int i = head[x]; i != -1; i = ne[i])
{
int u = e[i].u, v = e[i].v;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else
{
if (ins[v])
{
low[u] = min(low[u], dfn[v]);
}
}
}
if (low[x] == dfn[x])
{
++cnt;
int v;
do
{
v = stk.top(); stk.pop(), ins[v] = 0;
vis[v] = cnt;
dis_[cnt]+= dis[v];
} while (x != v);
}
}
2. 割点
去掉一个点之后,这个图不连通,这个点被称为割点。
【模板】割点(割顶)
题目背景
割点
题目描述
给出一个 n n n 个点, m m m 条边的无向图,求图的割点。
输入格式
第一行输入两个正整数 n , m n,m n,m。
下面 m m m 行每行输入两个正整数 x , y x,y x,y 表示 x x x 到 y y y 有一条边。
输出格式
第一行输出割点个数。
第二行按照节点编号从小到大输出节点,用空格隔开。
样例 #1
样例输入 #1
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
样例输出 #1
1 5
提示
对于全部数据, 1 ≤ n ≤ 2 × 1 0 4 1\leq n \le 2\times 10^4 1≤n≤2×104, 1 ≤ m ≤ 1 × 1 0 5 1\leq m \le 1 \times 10^5 1≤m≤1×105。
点的编号均大于 0 0 0 小于等于 n n n。
tarjan图不一定联通。
来自洛谷 P3388 【模板】割点(割顶)
dfn,low 作为标记。
child 计算当前节点的儿子个数。
割点的情况:
- 包含一棵树的节点的子节点的祖先仍然是父亲的子节点。
- 一个树的节点的儿子节点大于等于2。
void tarjan(int t, int fa)
{
dfn[t] = low[t] = ++cnt;
int child = 0;
for (int i = head[t]; i != -1; i = ne[i])
{
int u = e[i].u, v = e[i].v;
if (!dfn[v])
{
tarjan(v, fa);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != fa)
{
cut[u] = 1;
}
if (u == fa)
{
child++;
}
}
low[u] = min(low[u], dfn[v]);
}
if (child >= 2 && t == fa)
{
cut[t] = 1;
}
}