小指针

V1

2022/09/18阅读:7主题:凝夜紫

【图论专题】有向图的强连通分量的思路与应用

外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

有向图的强连通分量问题

对于一个有向图,它的连通分量:对于分量中 任意的两点u和v,都能从u走到v,并且可以从v走到u

强连通分量(SCC):极大连通分量,对于分量外的任意一点,加入分量,都会导致 该连通分量不再满足定义

强连通分量的作用将 有向图 通过 缩点 转换为 有向无环图(拓扑图)

缩点:将所有的连通分量缩为一个点。

在上图中,绿色部分就是强连通分量,所以我们可以把绿色部分缩点为一个点,同时其他四个单独的点,因为不和其他点相连,所以也符合强连通分量的定义,因此缩点后,整个图变成如下拓扑图的形式。

Tarjan算法求强连通分量

(ps: 关于这个部分,个人感觉真的是好难好难,可能也是之前没学过的原因,理解起来特别困难,在网上找了看了很多相关文章,大部分讲的都很好,但是并不适合初学者,希望我写的这个即便是初学者也能看完就懂。)

时间戳

这个时间戳不是真的表示时间的那个时间戳,它表示的含义是在图的深度优先搜索遍历过程中,在每个节点第一次遇到的时候,给这个节点一个整数标记,我们称这些整数标记时间戳

在该算法中,我们需要记录两个时间戳:

  1. dfn[u]:表示遍历到u时候的时间戳
  2. low[u]:表示从u开始走,所能遍历到的最小的时间戳 这里,想用这个图来带大家直观的感受一下low[u]数组的含义
    1. u=1的时候,low[u]是多少?根据low[u]数组的定义,毫无疑问是他自己,也就是low[1]=1
    2. u=2的时候,low[u]是多少?我们观察到图中绿色区域,其实是一个强连通分量,所以,根据强连通分量的定义(强连通分量中任意两点都是可以互相抵达的),我们知道2可以和1连通,那么根据low[u]数组的定义(low[2] 所能遍历到的最小时间戳就是 1),也就是low[2]=1;
    3. 同理,因为45都在绿色的强连通分量中,所以他们也都能到达1,所以有low[4]=1low[5]=1
    4. 而对于u=3来说,只有两个点可以到达,一个是他自己,一个是6,所以很明显,从3开始走,能到达的最小点就是他自己,所以low[3]=3;
    5. 而当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. 代码1:初始化dfn和low两个数组,这里如果不理解,请回看上面的定义;

  2. 代码2:stk[]数组存储遍历到的节点,in_stk[]数组记录节点u是否在stk数组中。所以这句代码的作用就是初始化,将当前节点u放到结构中,并在另一个标记数组中标记该节点u目前正在中。

  3. 代码3:假如子节点j没有被遍历过(没被遍历过就是dfn[j]=0),则进入递归。

  4. 代码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. 代码5:更新low[u]的第二处代码,我们首先要注意这句代码的进入时机,这句代码是在子节点已经被拥有编号并且仍然在stk中才会执行,注意子节点已经在stk里,说明这句代码也是需要在回溯阶段执行的。(至于子节点仍在stk中的意义是什么,请往后看。)

    因为ju的子节点,也就是说可以从u到达j,那么根据low[u]的定义,dfn[j]就可能成为u能到达的点中编号最小的点,所以要用dfn[j]更新low[u]是合理的。

  6. 代码6:还记得我们的重要性质吗?当触发代码6的时候,说明我们找到了一个强连通分量的开始,也就是说后面的代码,一定是把整个强连通分量都找出来。

  7. 代码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求传递闭包是一定会超时的,因此我们需要思考其他方案。

我们假设,本题是个有向无环图(拓扑图)

  1. 如果拓扑图存在两个点的出度为0,那么说明不存在牛满足目标。这点很好理解,因为这种情况,至少 出度为0的点 不会 被另一个出度为0的点 认为受欢迎。
  2. 如果只有一个点出度为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, -1sizeof 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. 最少需要多少个软件,直接给学校,才能让网络中所有学校都获得;
  2. 最少需要添加几个新的支援关系,才能让网络中,任意一个学校获得软件,其他所有学校也可以获得。

题目分析

问题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时:

  1. P==1的时候,表示只有一个起始点,那么这个起点,由于这个图是有向无环图,所以该起点必然可以走到每个终点,此时,我们只需要把每一个终点向起点连一条边,就可以使整个图变成强连通分量。通过下图,我们可以直观的看到,当从每个终点连接一条边(绿色)到起点后,整个图变成了强连通分量

  2. P>1的时候,必然可以找到两组点满足

    1. 某个起点P1可以走到某个终点Q1;
    2. 某个起点P2可以走到某个终点Q2;

    既,不同的起点,可以走到不同的终点

    这一点是论证结论的核心,为什么一定会有不同的起点走到不同的终点呢?因为是有向无环图,这种图的每个非起点必须有前驱节点,假如好多起点都走到同一个终点Q1,那么说明Q2是孤立的点,与有向无环图定义不符。

    这种情况下,我们把把某终点的边连接到某起点,这样子做会减少一个起点以及一个终点。

    原来有P个起点和Q个终点,每连接一条边都会使P-=1Q-=1,那么我们只要一共连接P-1条边,P就会变成1,此时Q会变成Q-(P-1)

    那么根据我们的大前提,Q是有可能大于P的。

    此时,P==1,Q>1,还需要加多少条边呢?这一点我们在上一步p==1时候已经求出来了,既,Q是多少就需要加多少条边,那么此时QQ-(P-1),所以也需要加这么多条边,再算上刚才增加的P-1条边,总共增加的边数量就是Q-(P-1)+(P-1)=Q

  3. 以上原理,是在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, -1sizeof 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 == 1puts("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

题目描述

本题主要由几个新的概念组成:

  1. 有向图半连通:强连通中,所有点两两之间,存在双向边,既,u指向v,v也必须指向u;而半连通中,所有点两两之间,存在单向边即可,u指向v 或者 v指向u 均可

  2. 导出子图:从原图中选出一些点和一些边,如果选出的边都是与选出点相关的,说明选出的是导出子图。其中“相关”的含义是选出边的两个点,均是选出点。

  3. 最大半连通子图:如果导出子图是半连通的,并且该导出子图,是原图所有导出子图中点数最多的

题目分析

根据题面给定的概念,我们能分析出一个重要的性质:

强连通子图一定是半连通子图,并且一个强连通图内部的最大半连通子图一定是该强连通图本身。

因此,我们可以利用这个性质。老规矩,先求出所有强连通子图,然后缩点,将原图变成有向无环图

在有向无环图中,每个强连通分量中的点一定是符合半连通的,所以我们主要看两个点不在同一个强连通分量的情况

这种情况下,如果两个强连通分量相连,说明这两个强连通分量必然是有点连接的,那么这两个强连通分量中的所有点,就可以通过相连接的点连起来,所以这俩强连通分量中的所有点,也是半连通子图.

那么,什么情况下,半连通图会不成立呢?两个点在有向无环图属于不同的分支

图中共有5个强连通分量,其中1号区域是强连通分量,所以1号区域中所有点都能走到绿色点;同理,2号区域所有点都能走到黄色点。又因为绿色点也能走到黄色点,所以1号区域所有点可以走到2号区域所有点,满足半连通

缩点成有向无环图后,我们发现形成了两条分支,而属于不同分支的两个区域35是不可达的,不满足半连通。所以这个有向无环图中,存在两个半连通子图

  1. 1->2->3;
  2. 1->2->4->5;

因为区域3,4,5,都是只有一个点,所以,很明显,第二个半连通子图是最大半连通子图。

总结一下思路:先找强连通分量,然后缩点成有向无环图,统计有向无环图中所有起点到终点的路线上,点数量最多的那个

Code

实现上,最后求点的数量最多的路线,可以使用动态规划的思路:

  1. f[i]表示以f[i]为结尾的点的最大数量,状态转移就是从i的所有前驱节点j中取f[j]的最大值。
  2. 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, -1sizeof h);
    memset(hs, -1sizeof 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

题目描述

(天空中最亮的⭐️⭐️~~~)

给出银河中不同⭐️⭐️之间的亮度关系,问我们所有⭐️⭐️的亮度值总和至少有多大。

题目分析

非常明显的一到差分约束题目。因此按照差分约束的思路先来分析下,本题求的是最小值,因此需要使用最大路,因此转换为边的符号是>=,我们先把题目条件转换成边:

  1. 如果 x=1 ,则 A=B ,那么有 A>=B,B>=A ;
  2. 如果 x=2 ,则 A<B ,那么有 B>=A+1 ;
  3. 如果 x=3 ,则 A>=B ,那么有 A>=B ;
  4. 如果 x=4 ,则 A>B ,那么有 A>=B+1 ;
  5. 如果 x=5 ,则 A<=B ,那么有 B>=A ;

按照之前的做法就是,先求spfa看下是否有正环,有正环则无解,然后spfa求最长路。除此之外的关键点是:

  1. 必须找到一个绝对条件,只有相对条件是没办法求最值的;
  2. 必须有一个超级源点可以到所有的边;

在上篇文章中我们使用了栈来优化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, -1sizeof h);
    memset(hs, -1sizeof 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

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1