基础知识

连通分量:对于分量中任意两点u,v 必然可以从u走到v 且从v走到u
强连通分量:极大连通分量

有向图的强连通分量无非是以下两种情况：

1.绿色：存在后向边指向祖先结点
2.红色：存在横插边指向的点有指向这两个点公共祖先节点
tarjan算法求强连通分量模板

void tarjan(int u)
{
	//dfn[u]dfs遍历到u的时间(如上图中的数字)
	//low[u]从u开始走所能遍历到的最小时间戳
    dfn[u] = low[u] = ++ timestamp; //打时间戳
    stk[++ top] = u; //入栈
    in_stk[u] = 1; //标记当前节点在栈中
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j]) //1.如果子节点未访问
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) //2.访问过且在栈中
        {
            low[u] = min(low[u], dfn[j]);
        }
        //3.如果访问过且不在栈中说明已经确定了强连通分量归属，这里不在考虑
    }
    if (dfn[u] == low[u]) //说明是某个强连通分量中编号最小的点
    {
        int y;
        ++ scc_cnt;
        do{
            y = stk[top -- ];
            in_stk[y] = 0;
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++ ;
        }while (y != u);
    }
}

从实际应用的角度来说，我们在求完强连通分量之后会进行缩点的操作。

for i=1;i<=n;i++
 for i的所有邻点j
   if i和j不在同一scc中:
    加一条新边id[i]→id[j]

缩点之后，该图就变成了有向无环图(拓扑图)了，这样处理起来就会很方便。

[USACO03FALL / HAOI2006] 受欢迎的牛 G

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $M$。

接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。

输出格式

一行单独一个整数，表示明星奶牛的数量。

输入输出样例 #1

输入 #1

3 3
1 2
2 1
2 3

输出 #1

1

说明/提示

只有 $3$ 号奶牛可以做明星。

【数据范围】

对于 $10\%$ 的数据，$N\le 20$，$M\le 50$。

对于 $30\%$ 的数据，$N\le 10^3$，$M\le 2\times 10^4$。

对于 $70\%$ 的数据，$N\le 5\times 10^3$，$M\le 5\times 10^4$。

对于 $100\%$ 的数据，$1\le N\le 10^4$，$1\le M\le 5\times 10^4$。

求强连通分量，缩点，得到拓扑图，这个拓扑图中，如果存在两个及以上出度为0的点，他们所包含的点一定无法相互到达，答案就为0；如果只存在一个出度为0的点，则统计出度为0的节点的数量。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 50010;
int h[N], e[M], ne[M], tot;
int dout[N];
int stk[N];
bool in_stk[N];
int id[N], scc_size[N];
int scc_cnt;
int top;
int dfn[N], low[N], timestamp;
int n, m;
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;
    in_stk[u] = 1;
    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] = 0;
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++ ;
        }while (y != u);
    }
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a] ++ ;
        }
    }
    int zeros = 0;
    int res = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
    {
        if (dout[i] == 0)
        {
            zeros ++ ;
            res += scc_size[i];
            if (zeros > 1)
            {
                res = 0;
                break;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

学校网络

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校$A$支援学校$B$，并不表示学校 $B$ 一定要支援学校 $A$）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

输入格式第 $1$ 行包含整数 $N$，表示学校数量。

第 $\mathrm{2..}N+1$ 行，每行包含一个或多个整数，第$i+1$行表示学校 i应该支援的学校名单，每行最后都有一个 $0$表示名单结束（只有一个 0即表示该学校没有需要支援的学校）。

输出格式
输出两个问题的结果，每个结果占一行。

数据范围
$2\le N\le 100$

输入样例：

5
2 4 3 0
4 5 0
0
0
1 0

输出样例：

1
2

求强连通分量，缩点，得到拓扑图。
在拓扑图中，我们把入度为0的点记作$P$,出度为0的点记作$Q$。
对于问题1，我们入读为0的点的个数就是答案，即$|P|$。
对于问题2，我们分$|P|\ge |Q|$和$|P|\le |Q|$两种情况进行考虑，以$|P|\le |Q|$为例。

1.$|P|=1$
我们需要把所有的终点都向起点连一条边，即答案为$|Q|$。

2.$|P|\ge 2$
一定存在两组起点和终点$p1,q1,p2,q2$，使得$p1$能够到达$q1$,$p2$能够到达$q2$。
证明：如果不成立，则说明所有的起点只能到达一个终点，而实际上终点的数量是$\ge 2$的,所以一定成立。
我们可以从$q1$到$p2$连一条边，这样一来就有$|P|=|P|-1$，$|Q|=|Q|-1$,以此类推，一直到$|P|=1$时，我们连了一共$|P|-1$条边，剩下了终点还有$|Q|-(|P|-1)$个，根据$|P|=1$的情况，说明还需要连$|Q|-(|P|-1)$条边。综上，还需要连的边数为$|Q|-(|P|-1)+|P|-1=|Q|$。
综上，需要连接$|Q|$条边。

$|P|\le |Q|$的情况同理可得，需要连$|P|$条边，综上，对于第二问答案为$min(|P|,|Q|)$。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = N * N;
int h[N], e[M], ne[M], tot;
int stk[N], top;
int dfn[N], low[N], id[N], timestamp, scc_cnt;
bool in_stk[N];
int din[N], dout[N];
int n;
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, in_stk[u] = 1;
    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] = 0;
            id[y] = scc_cnt;
        } while(u != y);
    }
}
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int t;
        while (cin >> t, t)
            add(i, t);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) din[b] ++ , dout[a] ++ ;
        }
    }
    int res1, res2;
    for (int i = 1; i <= scc_cnt; i ++ )
    {
        if (!din[i]) res1 ++ ;
        if (!dout[i]) res2 ++ ;
    }
    cout << res1 << endl;
    if (scc_cnt == 1) puts("0");
    else cout << max(res1, res2) << endl;
    return 0;
}

[ZJOI2007] 最大半连通子图

一个有向图 $G=\left(V,E\right)$ 称为半连通的 (Semi-Connected)，如果满足：$\forall u,v\in V$，满足 $u\to v$ 或 $v\to u$，即对于图中任意两点 $u,v$，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

若 $G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ 满足 $V^{\prime }\subseteq V$，$E^{\prime }$ 是 $E$ 中所有跟 $V^{\prime }$ 有关的边，则称 $G^{\prime }$ 是 $G$ 的一个导出子图。若 $G^{\prime }$ 是 $G$ 的导出子图，且 $G^{\prime }$ 半连通，则称 $G^{\prime }$ 为 $G$ 的半连通子图。若 $G^{\prime }$ 是 $G$ 所有半连通子图中包含节点数最多的，则称 $G^{\prime }$ 是 $G$ 的最大半连通子图。

给定一个有向图 $G$，请求出 $G$ 的最大半连通子图拥有的节点数 $K$，以及不同的最大半连通子图的数目 $C$。由于 $C$ 可能比较大，仅要求输出 $C$ 对 $X$ 的余数。

输入格式

第一行包含两个整数 $N,M,X$。$N,M$分别表示图 $G$ 的点数与边数，$X$ 的意义如上文所述。

接下来 $M$ 行，每行两个正整数 $a,b$，表示一条有向边 $\left(a,b\right)$。图中的每个点将编号为 $1,2,3\dots N$，保证输入中同一个$\left(a,b\right)$不会出现两次。

输出格式

应包含两行，第一行包含一个整数 $K$，第二行包含整数 $C\mathrm{mod}X$。

输入输出样例 #1

输入 #1

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

输出 #1

3
3

说明/提示

对于 $100\%$ 的数据，$N\le 10^5$，$M\le 10^6$，$X\le 10^8$。
求强连通分量，缩点，得到拓扑图。题目可以转化为找一条从起点到终点的最长路径，以及最长路径的数量。

#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], tot;
int dfn[N], low[N], timestamp;
int id[N], sz[N], scc_cnt;
int stk[N], top;
bool in_stk[N];
int f[N], g[N];
int n, m, x;
void add(int h[], int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, in_stk[u] = 1;
    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] = 0;
            id[y] = scc_cnt;
            sz[scc_cnt] ++ ;
        }while (y != u);
    }
}
int main()
{
    cin >> n >> m >> x;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(h, a, b);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) tarjan(i);
        
    unordered_set<ll>S;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            ll hash = a * 1000000ll + b;
            if (a != b && S.count(hash) == 0)
            {
                add(hs, a, b);
                S.insert(hash);
            }
        }
    }
    for (int i = scc_cnt; i >= 1; i -- )
    {
        if (!f[i])
        {
            f[i] = sz[i];
            g[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            if (f[k] < f[i] + sz[k])
            {
                f[k] = f[i] + sz[k];
                g[k] = g[i];
            }
            else if (f[k] == f[i] + sz[k])
                g[k] = (g[k] + g[i]) % x;
        }
    }
    int maxd = 0, cnt = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (maxd < f[i]) 
        {
            maxd = f[i];
            cnt = g[i];
        }
        else if (maxd == f[i])
            cnt = (cnt + g[i]) % x;
    cout << maxd << endl;
    cout << cnt << endl;
    return 0;
}

银河

银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 $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$。

输入输出样例 #1

输入 #1

5 7 
1 1 2 
2 3 2 
4 4 1 
3 4 5 
5 4 5 
2 3 5 
4 5 1

输出 #1

11

说明/提示

数据保证，$1\le N\le 100000$，$1\le M\le 100000$。
题中的不等关系如下,同时本题要求的是最小值，所以需要求最长路径。
$X=1,x_i=x_j\to x_i\ge x_j,x_j\ge x_i$
$X=2,x_i<x_j\to x_j\ge x_i+1$
$X=3,x_i\ge x_j$
$X=4,x_i>x_j\to x_i\ge x_j+1$
$X=5,x_i\le x_j\to x_j\ge x_i$
$x_i\ge 1\to x_i\ge x_0+1$
本问题如果用$spfa$会出现超时的情况，考虑求强连通分量，本问题无解等价于正环，因此我们在缩点过程中如果碰到在同一强连通分量中的两个点出现大于0的边权则说明无解。如果有解，我们就可以在拓扑图上$dp$从起点到各点的最长路径。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010, M = 400010;
int h[N], hs[N], e[M], ne[M], w[M], tot;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
ll d[N];
int dist[N];
int n, m;
void add(int h[], int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, in_stk[u] = 1;
    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 (low[u] == dfn[u])
    {
        int y;
        scc_cnt ++ ;
        do{
            y = stk[top --];
            in_stk[y] = 0;
            id[y] = scc_cnt;
            sz[scc_cnt] += 1;
        }while (u != y);      
    }
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    for (int i = 1; i <= m; i ++ )
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1) add(h, a, b, 0), add(h, b, a, 0);
        else if (t == 2) add(h, a, b, 1);
        else if (t == 3) add(h, b, a, 0);
        else if (t == 4) add(h, b, a, 1);
        else add(h, a, b, 0);
    }
    for (int i = 1; i <= n; i ++ )
        add(h, 0, i, 1);
    tarjan(0);
    int flag = 1;
    for (int i = 0; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a == b)
            {
                if (w[j] > 0)
                {
                    flag = 0;
                    break;
                }
            }
            else add(hs, a, b, w[j]);
        }
        if (!flag) break;
    }
    if (!flag) puts("-1");
    else{
        for (int i = scc_cnt; i >= 1; i -- )
        {
            for (int j = hs[i]; ~j; j = ne[j])
            {
                int k = e[j];
                d[k] = max(d[k], d[i] + w[j]);
            }
        }
        ll res = 0;
        for (int i = 1; i <= scc_cnt; i ++ )
        {
            res += d[i] * sz[i];
        }
        cout << res << endl;
    }
    return 0;
}