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

有向图的强连通分量问题

对于一个有向图，它的连通分量：对于分量中 「任意」的两点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. 同理，因为4和5都在绿色的「强连通分量」中，所以他们也都能到达1，所以有low[4]=1和low[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中的意义是什么，请往后看。）

   因为j是u的子节点，也就是说可以从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, -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. 「最少」需要多少个软件，直接给学校，才能让网络中所有学校都获得；
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-=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。

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, -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

题目描述

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

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

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

3. 最大半连通子图：如果「导出子图是半连通的，并且该导出子图，是原图所有导出子图中点数最多的」。

题目分析

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

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

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

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

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

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

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

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

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, -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

题目描述

（天空中最亮的⭐️⭐️~~~）

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

题目分析

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

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, -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」