首页 算法 图论

# 有向图的强连通分量问题

对于一个有向图，它的连通分量：对于分量中 任意的两点 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 是怎么更新出来的呢？没错，就是这句代码 4 low[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 是受欢迎的。

目标是 求出 有多少头牛 被除自己之外的所有牛 都认为是受欢迎的。

# 题目分析

根据题目描述，一下就能看出来，这是一个传递闭包的题目，但是看一下数据范围：点的范围是10410^4 ，边的范围是5∗1045*10^4，如果使用 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