小指针
2022/09/18阅读:117主题:凝夜紫
【图论专题】有向图的强连通分量的思路与应用
外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。
有向图的强连通分量问题
对于一个有向图,它的连通分量:对于分量中 「任意」的两点u和v,都能「从u走到v,并且可以从v走到u」。
强连通分量(SCC):「极大连通分量」,对于「分量外的任意一点,加入分量,都会导致 该连通分量不再满足定义」。
强连通分量的「作用」是「将 有向图 通过 缩点 转换为 有向无环图(拓扑图)」。
「缩点」:将所有的「连通分量」缩为一个点。
在上图中,绿色部分就是「强连通分量」,所以我们可以把绿色部分「缩点」为一个点,同时其他四个单独的点,因为「不和其他点相连」,所以也符合「强连通分量」的定义,因此「缩点」后,整个图变成如下「拓扑图」的形式。
Tarjan算法求强连通分量
(ps: 关于这个部分,个人感觉真的是好难好难,可能也是之前没学过的原因,理解起来特别困难,在网上找了看了很多相关文章,大部分讲的都很好,但是并不适合初学者,希望我写的这个即便是初学者也能看完就懂。)
时间戳
这个时间戳不是真的表示时间的那个时间戳,它表示的含义是「在图的深度优先搜索遍历过程中,在每个节点第一次遇到的时候,给这个节点一个整数标记」,我们称这些「整数标记」为「时间戳」。
在该算法中,我们需要记录两个时间戳:
-
dfn[u]
:表示「遍历到u时候的时间戳」; -
low[u]
:表示「从u开始走,所能遍历到的最小的时间戳」;这里,想「用这个图来带大家直观的感受一下low[u]数组的含义」:
-
当 u=1
的时候,low[u]
是多少?根据「low[u]数组的定义」,毫无疑问是他自己,也就是low[1]=1
; -
当 u=2
的时候,low[u]
是多少?我们观察到图中绿色区域,其实是一个「强连通分量」,所以,根据强连通分量的定义(「强连通分量中任意两点都是可以互相抵达的」),我们知道2
可以和1
连通,那么根据low[u]数组
的定义(「low[2] 所能遍历到的最小时间戳就是 1」),也就是low[2]=1
; -
同理,因为 4
和5
都在绿色的「强连通分量」中,所以他们也都能到达1
,所以有low[4]=1
和low[5]=1
; -
而对于 u=3
来说,只有两个点可以到达,一个是他自己,一个是6
,所以很明显,从3
开始走,能到达的最小点就是他自己,所以low[3]=3
; -
而当 u=6
,它就只能到达它自己了,所以low[6]=6
;
-
通过上面的两个时间戳数组,我们可以得出一个重要性质:「u是其所在强连通分量的“最高点”,等价于 dfn[u]==low[u];」
如果能顺利的理解low[u]
的含义,相信大家就不难理解这句话的含义了。
如上图中的三个「强连通分量」:{1,2,4,5
},{3
},{6
}中,都是当dfn[u]
在“最高点”或者叫“最靠前的点”的时候,「标志着一个 强连通分量 的开始(官方一点叫做 强连通分量子图的最小根)」。
那么,tarjan同学是「如何从一个强连通分量的开始,将整个强连通分量都找出来呢?」
其实秘密就在于他使用了「栈」的结构。
模板Code
首先,要说明的是:tarjan同学求「强连通分量的算法是基于图的DFS遍历的」,所以我们先回顾一下图的DFS遍历,假设我们给图中所有的节点都设置一个时间戳,也就是求出dfn[u]
数组。
void dfs(int u) {
dfs[u] = ++ timestamp; // 给当前节点一个编号
// 遍历当前节点u的所有子节点
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
dfs(j); // 递归搜索所有子节点
}
// 当前分支搜索到底,也就是程序运行到这里的时候,
// 当前的u就是叶子节点,如果没有其他处理,
// 程序会因为所有语句执行完成而隐性的回溯,返回到上一个dfs(u)
}
如果读者已经完全的理解上面的「图的DFS遍历」,则可以继续看下面tarjan同学写的传世经典。
// tarjan求scc
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp; // 代码1
stk[ ++ top] = u, in_stk[u] = true; // 代码2
// 遍历出u的所有子节点j
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dfn[j]) { // 代码3
tarjan(j); // DFS序的遍历
low[u] = min(low[u], low[j]); // 代码4
} else if (in_stk[j]) {
low[u] = min(low[u], dfn[j]); // 代码5
}
}
if (dfn[u] == low[u]) { // 代码6
int y;
++ scc_cnt; // 给 强连通分量 设置一个编号
do { // 代码7开始
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
} while {y != u}; // 代码7结束
}
}
-
代码1:初始化dfn和low两个数组,这里如果不理解,请回看上面的定义;
-
代码2:
stk[]
数组存储遍历到的节点,in_stk[]
数组记录节点u是否在stk数组中。所以这句代码的作用就是「初始化」,将「当前节点u」放到「栈」结构中,并在另一个「标记数组」中标记该节点u
目前正在「栈」中。 -
代码3:假如子节点
j
没有被遍历过(没被遍历过就是dfn[j]=0),则进入递归。 -
代码4:「更新low[u]的第一处代码」,从这句开始,变得烧脑了。这里为啥要用low[子节点]去更新low[父节点]呢?
注意这句代码的位置,它是在递归之后的,也就是「搜索完当前分支并回溯的时候,才开始执行的」。
设想,以上面的low[u]数组讲解中的「强连通分量 3 和 6」为例,当
u=3
的时候j=6
,并且有low[3]=3
,这个low[3]=3
是怎么更新出来的呢?没错,就是这句代码4low[u] = min(low[u], low[j]);
更新出来的。而从意义来看,
low[u]
表示u
所能到达的点中编号最小的点,而j
本来就是u
所能到达的点,所以low[j]
是完全有可能更新low[u]
的。综上所述,代码4存在的原因,我们就找到了,因为DFS遍历是必须回溯的,所以可以在「回溯」的时候「通过比较父节点和子节点的low数组,来更新父节点的low数组」。
-
代码5:「更新low[u]的第二处代码」,我们首先要注意这句代码的进入时机,这句代码是「在子节点已经被拥有编号并且仍然在stk中」才会执行,注意子节点已经在
stk
里,说明「这句代码也是需要在回溯阶段执行的」。(至于子节点仍在stk中的意义是什么,请往后看。)因为
j
是u
的子节点,也就是说可以从u
到达j
,那么根据low[u]
的定义,dfn[j]
就可能成为u
能到达的点中编号最小的点,所以要用dfn[j]
更新low[u]
是合理的。 -
代码6:还记得我们的重要性质吗?当触发
代码6
的时候,说明我们找到了一个「强连通分量的开始」,也就是说后面的代码,一定是把整个强连通分量都找出来。 -
代码7:整个do...while循环都在做一件事情,「把整个强连通分量找出来」。
如果想找出一个范围区间(类比强连通分量),我们需要知道什么?从直觉上来看,我们需要知道区间的起始节点和终止节点,由这两个节点来确定一个区间。事实上的确如此,但是如果我们把区间加入到数据结构「栈」中就变得不需要两个节点了,我们只需要知道一个起始节点就可以了,因为「我们可以从当前起始节点开始出栈,一直到下一个起始节点终止,这样所有出栈的元素,其实就是属于同一个区间」,在这个过程中,我们只需要知道每个区间的起始节点,而不需要知道终止节点。
明白了这个原理之后,读者再来看代码7这段代码片段,是否有种霍然开朗的感觉呢?
注意,代码7的执行时机是「一个分支全部搜索结束的时候」,做的事情实际上就是在「栈顶弹出元素,直到弹出的元素是 起始节点(当前u),说明我们就找到了以当前u为最小根的强连通分量」!
缩点
缩点的概念前面已经有描述。此处只要想给出缩点的具体实现。
模板Code
// 遍历所有点
for (int u = 1; u <= n; u ++ ) {
for (int i = h[u]; ~i; i = ne[i]) {
// j是u的子节点
int j = e[i];
// 如果u和j不在一个强连通分量
if (id[u] != id[j]) {
// 点u的出度 ++
dout[id[u]] ++ ;
}
}
}
AcWing 1174. 受欢迎的牛
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 N 头牛,编号从 1 到 N,给你 M 对整数 (A,B),表示牛 A 认为牛 B 受欢迎。
这种关系是具有传递性的,如果 A 认为 B 受欢迎,B 认为 C 受欢迎,那么牛 A 也认为牛 C 受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
「输入格式」 第一行两个数 N,M;
接下来 M 行,每行两个数 A,B,意思是 A 认为 B 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A,B)。
「输出格式」 输出被除自己之外的所有牛认为是受欢迎的牛的数量。
「数据范围」
1≤N≤10^4, 1≤M≤5×10^4
「输入样例」
3 3 1 2 2 1 2 3
「输出样例」
1
「样例解释」
只有第三头牛被除自己之外的所有牛认为是受欢迎的。
题目描述
给出N头牛,编号1~N,给出M个整数对{A,B},表示A认为B是受欢迎的,并且这些整数对表达的关系具有「传递性」,既,如果A认为B是受欢迎的,B认为C是受欢迎的,那么A自动的认为C是受欢迎的。
「目标是 求出 有多少头牛 被除自己之外的所有牛 都认为是受欢迎的」。
题目分析
根据题目描述,一下就能看出来,这是一个「传递闭包」的题目,但是看一下数据范围:点的范围是 ,边的范围是 ,如果使用「floyd求传递闭包」是一定会超时的,因此我们需要思考其他方案。
我们假设,本题是个「有向无环图(拓扑图)」:
-
如果拓扑图存在两个点的出度为0,那么说明不存在牛满足目标。这点很好理解,因为这种情况,至少 出度为0的点 不会 被另一个出度为0的点 认为受欢迎。 -
如果只有一个点出度为0,那么就表示「其他所有点多能走到这个出度为0的点」,也就是其他所有牛都认为它是受欢迎的。
那么,如何把题目给出的图,变成「拓扑图」呢?这就要用到,我们本文讲的「强连通分量」和「缩点」啦。
缩点后,拓扑图中所有点都是一个强连通分量,那么出度为0的那个强连通分量中的所有点就是目标所求的点。
「因为,出度为0,说明其他的强连通分量所代表的点都能走到这个点」,这个点也代表一个「强连通分量」,那么根据连通分量定义,「这个强连通分量点中的所有点都互相可达」,所以这个出度为0的强连通分量中的所有点都是目标所求的点,统计个数即可。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 50010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top, id[N], scc_cnt;
bool in_stk[N];
int n, m, Size[N], dout[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[j], low[u]);
} else if (in_stk[j]) {
low[u] = min(dfn[j], low[u]);
}
}
if (low[u] == dfn[u]) {
int y;
++ scc_cnt;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
// 记录每个强联通分量中点的数量
Size[scc_cnt] ++ ;
} while (y != u);
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
// tarjan 遍历出所有的强联通份量
for (int i = 1; i <= n; i ++ ) {
if (!dfn[i]) tarjan(i);
}
// 缩点
for (int u = 1; u <= n; u ++ ) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
int a = id[u], b = id[j];
// a的出度 +1
if (a != b) dout[a] ++ ;
}
}
int zeros = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ ) {
if (!dout[i]) {
zeros ++ ;
sum += Size[i];
if (zeros > 1) {
sum = 0;
break;
}
}
}
printf("%d\n", sum);
return 0;
}
AcWing 367. 学校网络
一些学校连接在一个计算机网络上,学校之间存在软件支援协议,每个学校都有它应支援的学校名单(学校 A 支援学校 B,并不表示学校 B 一定要支援学校 A)。
当某校获得一个新软件时,无论是直接获得还是通过网络获得,该校都应立即将这个软件通过网络传送给它应支援的学校。
因此,一个新软件若想让所有学校都能使用,只需将其提供给一些学校即可。
现在请问最少需要将一个新软件直接提供给多少个学校,才能使软件能够通过网络被传送到所有学校?
最少需要添加几条新的支援关系,使得将一个新软件提供给任何一个学校,其他所有学校就都可以通过网络获得该软件?
「输入格式」 第 1 行包含整数 N,表示学校数量。
第 2..N+1 行,每行包含一个或多个整数,第 i+1 行表示学校 i 应该支援的学校名单,每行最后都有一个 0 表示名单结束(只有一个 0 即表示该学校没有需要支援的学校)。
「输出格式」 输出两个问题的结果,每个结果占一行。
「数据范围」
2≤N≤100
「输入样例」
5 2 4 3 0 4 5 0 0 0 1 0
「输出样例」
1 2
题目描述
一些学校在一个计算机网络上,一些学校之间有一个软件支援规则,给出A支援B(有向图),最重要的规则是「无论这个学校是直接获得的软件,还是网络中别的学校传给它的,它都需要第一时间传给所有它能传到的学校」,最终的问题有两个:
-
「最少」需要多少个软件,直接给学校,才能让网络中所有学校都获得; -
「最少」需要添加几个新的支援关系,才能让网络中,任意一个学校获得软件,其他所有学校也可以获得。
题目分析
问题1
我们可以通过观察给定示例,来找到这个问题的答案。
根据题面中的给定示例,我们可以画出如上图。我们发现想让所有的学校都获得软件,只需要给
1
号点即可,因为「1号点可以传给2,3,4,而2号点接到后,又会传给5号点,至此,所有的学校都获得了软件」。
对于上面的图,我们比较容易发现一个规律,在一个「有向无环图」内,图中所有的节点是否都能收到软件,关键在于「节点的起点是否收到软件」,所以,我们「只需要找到给定图的所有 强连通分量,通过 缩点,把给 定图 转换为 有向无环图,然后统计有多少个起点即可。」
问题2
根据问题,我们想让「任何一个点获得软件,那么其他所有点都获得软件」,毫无疑问,这就说明「图中所有的点必须都是两两连通的」,只有这样,才能满足问题条件,也就是说 整个图形成一个「强连通分量」。
观察示例中的图,我们发现1,2,5
是一个「强连通分量」,而1
号点可以到达所有点,所以2,5
号点也可以到达所有点(根据强连通分量定义),那么「就只有3和4是无法和其他点连通的,我们把它俩都指向起点(绿色边),这样整个图就全部联通了」。
在第一问中,我们已经把整个图变成了一个「有向无环图」,我们假设这个图有P个起点(入度为0),Q个终点(出度为0)。
对于问题:「一个有向无环图,最少加几条边,可以使他变成 强连通分量」,是有一个明确的结论的。
假设一个图是「有向无环图,有P个起点,Q个终点」,那么想让该图变成「强连通分量」,至少要添加
max(P,Q)
条边。
如何论证这个结论呢?我们可以分两步来看,我们假设P<=Q
时:
-
当
P==1
的时候,表示只有一个起始点,那么这个起点,由于这个图是有向无环图,所以该起点必然可以走到每个终点,此时,我们「只需要把每一个终点向起点连一条边,就可以使整个图变成强连通分量」。通过下图,我们可以直观的看到,当从每个终点连接一条边(绿色)到起点后,整个图变成了「强连通分量」。 -
当
P>1
的时候,「必然可以找到两组点满足」:-
「某个起点P1可以走到某个终点Q1;」 -
「某个起点P2可以走到某个终点Q2;」
「既,不同的起点,可以走到不同的终点」。
这一点是论证结论的核心,为什么一定会有不同的起点走到不同的终点呢?因为是
有向无环图
,这种图的每个非起点必须有前驱节点,假如好多起点都走到同一个终点Q1,那么说明Q2是孤立的点,与有向无环图定义不符。这种情况下,我们把「把某终点的边连接到某起点」,这样子做会「减少一个起点以及一个终点。」
原来有
P
个起点和Q
个终点,每连接一条边都会使P-=1
和Q-=1
,那么我们只要一共连接P-1
条边,P
就会变成1
,此时Q
会变成Q-(P-1)
;那么根据我们的大前提,「Q是有可能大于P」的。
此时,
P==1
,Q>1
,还需要加多少条边呢?这一点我们在上一步p==1
时候已经求出来了,既,「Q是多少就需要加多少条边」,那么此时Q
是Q-(P-1)
,所以也需要加这么多条边,再算上刚才增加的P-1
条边,总共增加的边数量就是Q-(P-1)+(P-1)=Q
。 -
-
以上原理,是在
P<=Q
的大前提下成立的,那么我们反过来P>=Q
也是成立的,所以,就有最后的结论:max(Q, P)
;
Code
#include <iostream>
#include <cstring>
using namespace std;
// 边的极限数量,每个点都是孤立的,也就需要N^2条边;
const int N = 110, M = N * N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, din[N], dout[N];
int n;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
} else if (in_stk[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
++ scc_cnt;
int y;
do {
y = stk[top -- ];
id[y] = scc_cnt;
in_stk[y] = false;
} while (y != u);
}
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) {
int a;
while (cin >> a, a) add(i, a);
}
// 求所有的 强连通分量
for (int i = 1; i <= n; i ++ )
if (!dfn[i]) tarjan(i);
// 缩点
for (int u = 1; u <= n; u ++ ) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
int a = id[u], b = id[j];
// a 向 b 连接 则a的出度 ++; b的入度 ++ ;
if (a != b) dout[a] ++ , din[b] ++ ;
}
}
int P = 0, Q = 0;
for (int i = 1; i <= scc_cnt; i ++ ) {
if (!din[i]) P ++ ; // 没有入度 说明是起点
if (!dout[i]) Q ++ ; // 没有出度 说明是终点
}
printf("%d\n", P); // 问题1 统计起点
//特判 如果整个图本来就是 一个强连通分量 则不需要加任何的边
if (scc_cnt == 1) puts("0");
else printf("%d", max(P, Q)); // 问题2
return 0;
}
AcWing 1175. 最大半连通子图
一个有向图 G=(V,E) 称为半连通的 (Semi-Connected),如果满足:∀u,v∈V,满足 u→v 或 v→u,即对于图中任意两点 u,v,存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。
若 G′=(V′,E′) 满足,E′ 是 E 中所有和 V′ 有关的边,则称 G′ 是 G 的一个导出子图。
若 G′ 是 G 的导出子图,且 G′ 半连通,则称 G′ 为 G 的半连通子图。
若 G′ 是 G 所有半连通子图中包含节点数最多的,则称 G′ 是 G 的最大半连通子图。
给定一个有向图 G,请求出 G 的最大半连通子图拥有的节点数 K,以及不同的最大半连通子图的数目 C。
由于 C 可能比较大,仅要求输出 C 对 X 的余数。
「输入格式」
第一行包含三个整数 N,M,X。N,M 分别表示图 G 的点数与边数,X 的意义如上文所述;接下来 M 行,每行两个正整数 a,b,表示一条有向边 (a,b)。
图中的每个点将编号为 1 到 N,保证输入中同一个 (a,b) 不会出现两次。
「输出格式」
应包含两行。第一行包含一个整数 K,第二行包含整数 C mod X。
「数据范围」
1≤N≤10^5, 1≤M≤10^6, 1≤X≤10^8
「输入样例」
6 6 20070603 1 2 2 1 1 3 2 4 5 6 6 4
「输出样例」
3 3
题目描述
本题主要由几个新的概念组成:
-
有向图半连通:「强连通中,所有点两两之间,存在双向边,既,u指向v,v也必须指向u;而半连通中,所有点两两之间,存在单向边即可,u指向v 或者 v指向u 均可」,
-
导出子图:「从原图中选出一些点和一些边,如果选出的边都是与选出点相关的,说明选出的是导出子图」。其中“相关”的含义是选出边的两个点,均是选出点。
-
最大半连通子图:如果「导出子图是半连通的,并且该导出子图,是原图所有导出子图中点数最多的」。
题目分析
根据题面给定的概念,我们能分析出一个重要的性质:
「强连通子图一定是半连通子图,并且一个强连通图内部的最大半连通子图一定是该强连通图本身。」
因此,我们可以利用这个性质。老规矩「,先求出所有强连通子图,然后缩点,将原图变成有向无环图」。
在有向无环图中,每个强连通分量中的点一定是符合半连通的,所以我们主要看「两个点不在同一个强连通分量的情况」。
这种情况下,如果「两个强连通分量相连」,说明这「两个强连通分量必然是有点连接的」,那么这两个强连通分量中的所有点,就可以通过相连接的点连起来,所以这俩「强连通分量中的所有点,也是半连通子图」.
那么,什么情况下,半连通图会不成立呢?「两个点在有向无环图属于不同的分支」。
图中共有5个强连通分量,其中1号区域是强连通分量,所以1号区域中所有点都能走到绿色点;同理,2号区域所有点都能走到黄色点。又因为绿色点也能走到黄色点,所以1号区域所有点可以走到2号区域所有点,满足「半连通」。
「缩点」成有向无环图后,我们发现形成了两条分支,而属于不同分支的两个区域
3
和5
是不可达的,不满足半连通。所以这个「有向无环图」中,存在「两个半连通子图」:
-
1->2->3; -
1->2->4->5;
因为区域3,4,5
,都是只有一个点,所以,很明显,第二个半连通子图是最大半连通子图。
总结一下思路:「先找强连通分量,然后缩点成有向无环图,统计有向无环图中所有起点到终点的路线上,点数量最多的那个」。
Code
实现上,最后求点的数量最多的路线,可以使用动态规划的思路:
-
f[i]表示以f[i]为结尾的点的最大数量,状态转移就是从i的所有前驱节点j中取f[j]的最大值。 -
g[i]表示以f[i]的路线数量。
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 100010, M = 2000010;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp, stk[N], top, scc_cnt;
bool in_stk[N];
int id[N], Size[N]; // Size表示每个强连通分量中点的数量
int n, m, X;
int f[N], g[N];
void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
} else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
int y;
++ scc_cnt;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++ ;
} while (y != u);
}
}
int main() {
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
cin >> n >> m >> X;
while (m -- ) {
int a, b;
scanf("%d%d", &a, &b);
add(h, a, b);
}
for (int i = 1; i <= n; i ++ )
if (!dfn[i]) tarjan(i);
// 用来判断边是否重复 哈希函数 (v, u) -> v * 1000000 + u
unordered_set<LL> S;
for (int u = 1; u <= n; u ++ )
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
int a = id[u], b = id[j];
LL hash = a * 1000000ll + b; // 乘法可能爆int 转LL
if (a != b && !S.count(hash)) {
S.insert(hash);
add(hs, a, b);
}
}
// 遍历新图(缩点后的有向无环图) 计算
for (int u = scc_cnt; u; u -- ) {
// 未被更新过的f[u]就是起点 初始化起点
if (!f[u]) {
f[u] = Size[u];
g[u] = 1;
}
// 遍历 u能到达的点 j
for (int i = hs[u]; ~i; i = ne[i]) {
int j = e[i];
// 状态转移 f[j] 等于它的父节点的总点数f[u]+它自己的点数scc_cnt[j]
if (f[j] < f[u] + Size[j]) {
f[j] = f[u] + Size[j];
g[j] = g[u]; // 从u到j 方案无法增加
} else if (f[j] == f[u] + Size[j]) {
// 当转移方程相等的时候 说明f[u] + scc_cnt[j] 也是一种最大值方案
// 所以需要进行累加 g[j] += g[u]
g[j] = (g[j] + g[u]) % X;
}
}
}
int maxf = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ ) {
if (maxf < f[i]) {
maxf = f[i];
sum = g[i];
} else if (maxf == f[i]) {
sum = (sum + g[i]) % X;
}
}
printf("%d\n", maxf);
printf("%d\n", sum);
return 0;
}
AcWing 368. 银河
银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是 1。
现在对于 N 颗我们关注的恒星,有 M 对亮度之间的相对关系已经判明。
你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。
「输入格式」
第一行给出两个整数 N 和 M。之后 M 行,每行三个整数 T,A,B,表示一对恒星 (A,B) 之间的亮度关系。恒星的编号从 1 开始。
如果 T=1,说明 A 和 B 亮度相等。 如果 T=2,说明 A 的亮度小于 B 的亮度。 如果 T=3,说明 A 的亮度不小于 B 的亮度。 如果 T=4,说明 A 的亮度大于 B 的亮度。 如果 T=5,说明 A 的亮度不大于 B 的亮度。
「输出格式」
输出一个整数表示结果。若无解,则输出 −1。
「数据范围」
N≤100000,M≤100000
「输入样例」
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
「输出样例」
11
题目描述
(天空中最亮的⭐️⭐️~~~)
给出银河中不同⭐️⭐️之间的亮度关系,问我们所有⭐️⭐️的亮度值总和至少有多大。
题目分析
非常明显的一到差分约束题目。因此按照差分约束的思路先来分析下,本题求的是最小值,因此需要使用最大路,因此转换为边的符号是>=
,我们先把题目条件转换成边:
-
如果 x=1 ,则 A=B ,那么有 A>=B,B>=A ; -
如果 x=2 ,则 A<B ,那么有 B>=A+1 ; -
如果 x=3 ,则 A>=B ,那么有 A>=B ; -
如果 x=4 ,则 A>B ,那么有 A>=B+1 ; -
如果 x=5 ,则 A<=B ,那么有 B>=A ;
按照之前的做法就是,先求spfa看下是否有正环,有正环则无解,然后spfa求最长路。除此之外的关键点是:
-
必须找到一个 绝对条件
,只有相对条件是没办法求最值的; -
必须有一个超级源点可以到所有的边;
在上篇文章中我们使用了栈来优化spfa,这是因为spfa的时间复杂度是O(km)~O(nm),会被出题人用数据卡掉,本文我们学了强连通分量后,可以使用强连通分量来解决。
考虑如果存在正环,那么正环必然是在强连通分量中,而强连通分量中的环,如果合法一定满足三角不等式:如d[1]>=d[2]>=d[3]>=d[1]
,如何才能让这种三角不等式满足?那就必须是所有的边权重全部是0
(参考当x=1
的时候),也就是说:「不存在正环,则强连通分量中的每条边必须等于0」。
「下一步,在有向无环图上求最长路,就比较简单了,只需要从前往后递推一下即可。」
Code
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010, M = 600010;
int n, m;
int h[N], hs[N], w[M], e[M], ne[M], idx;
int dfn[N], low[N], stk[N], id[N], Size[N], timestamp, scc_cnt, top;
bool in_stk[N];
int dist[N]; // 有向无环图中点之间的最长路径
void add(int h[], int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
} else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
int y;
++ scc_cnt;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++ ;
} while (y != u);
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
// 建立超级源点 从0号点 向其他所有点连接一条长度为1的边
for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1);
while (m -- ) {
int t, a, b;
scanf("%d%d%d", &t, &a, &b);
if (t == 1) add(h, b, a, 0), add(h, a, b, 0);
if (t == 2) add(h, a, b, 1);
if (t == 3) add(h, b, a, 0);
if (t == 4) add(h, b, a, 1);
if (t == 5) add(h, a, b, 0);
}
// 因为0号点可以到所有其他点,所以从0号点做tarjan就可以了。
tarjan(0);
bool flag = true; // 判断有没有解
for (int u = 0; u <= n; u ++ ) { // 注意这里的下标 要从点0开始
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
int a = id[u], b = id[j];
if (a == b && w[i] > 0) {
flag = false;
break;
} else add(hs, a, b, w[i]);
}
if (!flag) break;
}
if (!flag) puts("-1");
else {
// tarjan之后 倒着遍历 就是拓扑序
for (int u = scc_cnt; u; u -- ) {
for (int i = hs[u]; ~i; i = ne[i]) {
int j = e[i];
dist[j] = max(dist[j], dist[u] + w[i]);
}
}
LL res = 0;
for (int i = 1; i <= scc_cnt; i ++ ) {
// 同一个强连通分量中的所有点 到它的后继强连通分量的 最长路径都相等
res += (LL)dist[i] * Size[i];
}
printf("%lld", res);
}
return 0;
}
「END」
作者介绍