强连通分量

定义

什么是强连通
在有向图中，如果A可以到B，B可以到A，那么A和B是强连通的
强连通满足传递性，如果A和B是强连通的，B和C是强连通的，那么A和C也是强连通的
强连通分量，如果一些点之间两两是强连通的，那么称这些点为强连通分量
如果一个强连通分量中，再加入任何点都不再是强连通分量了，那么叫做极大强连通分量
每个点只属于一个极大强连通分量
可以把所有点划分成若干个强连通分量，这个算法叫做缩点

Tarjan 算法

每个点维护 dfs 和 low 两个标记

dfs时遇到每个点，有3种情况

  1. 从未被访问过 !dfn[y]
    tarjan(y);
    low[x] = min(low[x], low[y])
  2. 已经被访问，还未出栈 v[y]
    low[x] = min(low[x], dfn[y])
  3. 已经被访问，已经出栈
    忽略

对于每个点，枚举所有出边之后
如果 dfn == low
那么当前子树是一个强连通分量

Kosaraju 算法

参考题目

P1726 上白泽慧音

https://www.luogu.com.cn/problem/P1726

题目描述

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。

输入格式

第1行：两个正整数N,M

第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出格式

第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。

第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

样例 #1

样例输入 #1
5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1
样例输出 #1
3
1 3 5

提示

对于60%的数据：N <= 200且M <= 10,000

对于100%的数据：N <= 5,000且M <= 50,000

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
int c[100020];
int n, m, x, y, z, cnt;
int dfn[100020];
int low[100020];
int stk[100020], ss;
int v[100020];
int r[100020], scc;
void tarjan(int x)
{
	dfn[x] = low[x] = ++cnt;
	stk[ss++] = x;
	v[x] = 1;
	for (int y: a[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (v[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		scc++;
		int u;
		do
		{
			u = stk[--ss];
			r[u] = scc;
			v[u] = 0;
		}
		while (u != x);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(y);
		if (z == 2)
		{
			a[y].push_back(x);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		c[r[i]]++;
	}
	int ans = 0, ansr;
	for (int i = 1; i <= n; i++)
	{
		if (ans < c[r[i]])
		{
			ans = c[r[i]];
			ansr = r[i];
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i <= n; i++)
	{
		if (r[i] == ansr)
		{
			printf("%d ", i);
		}
	}
	printf("\n");
	return 0;
}

题解

P1262 间谍网络

https://www.luogu.com.cn/problem/P1262

题目描述

由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 nn 个间谍（nn 不超过 30003000），每个间谍分别用 11 到 30003000 的整数来标识。

请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入格式

第一行只有一个整数 nn。

第二行是整数 pp。表示愿意被收买的人数，1≤p≤n1\le p\le n。

接下来的 pp 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过 2000020000。

紧跟着一行只有一个整数 rr，1≤r≤80001\le r\le8000。然后 rr 行，每行两个正整数，表示数对 (A,B)(A, B)，AA 间谍掌握 BB 间谍的证据。

输出格式

如果可以控制所有间谍，第一行输出 YES，并在第二行输出所需要支付的贿金最小值。否则输出 NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

样例 #1

样例输入 #1
3
2
1 10
2 100
2
1 3
2 3
样例输出 #1
YES
110

样例 #2

样例输入 #2
4
2
1 100
4 200
2
1 2
3 4
样例输出 #2
NO
3

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
int in[100020];
int n, m, x, y, cnt;
int dfn[100020];
int low[100020];
int stk[100020], ss;
int v[100020];
int r[100020], scc;
int w[100020];
int f[100020];
void tarjan(int x)
{
	dfn[x] = low[x] = ++cnt;
	stk[ss++] = x;
	v[x] = 1;
	for (int y: a[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (v[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		scc++;
		int u;
		do
		{
			u = stk[--ss];
			r[u] = scc;
			v[u] = 0;
		}
		while (u != x);
	}
}
void work()
{
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i] && w[i] < 1e9)
		{
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			printf("NO\n");
			printf("%d\n", i);
			return;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j: a[i])
		{
			if (r[i] != r[j])
			{
				in[r[j]]++;
			}
		}
		f[r[i]] = min(f[r[i]], w[i]);
	}
	int ans = 0;
	for (int i = 1; i <= scc; i++)
	{
		if (!in[i])
		{
			ans += f[i];
		}
	}
	printf("YES\n");
	printf("%d\n", ans);
	return;
}
int main()
{
	scanf("%d", &n);
	scanf("%d", &m);
	memset(w, 0x3f, sizeof w);
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		w[x] = y;
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
	}
	work();
	return 0;
}

题解

P2002 消息扩散

https://www.luogu.com.cn/problem/P2002

题目背景

本场比赛第一题，给个简单的吧，这 100 分先拿着。

题目描述

有 nn 个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出 nn 个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有 nn 个城市都得到消息。

输入格式

第一行两个整数 n,mn, m，表示 nn 个城市，mm 条单向道路。

以下 mm 行，每行两个整数 b,eb, e 表示有一条从 bb 到 ee 的道路，道路可以重复或存在自环。

输出格式

一行一个整数，表示至少要在几个城市中发布消息。

样例 #1

样例输入 #1
5 4
1 2
2 1
2 3
5 1
样例输出 #1
2

提示

【样例解释 #1】

样例中在 4,54, 5 号城市中发布消息。

【数据范围】

对于 20%20 \% 的数据，n≤200n \le 200；
对于 40%40 \% 的数据，n≤2000n \le 2000；
对于 100%100 \% 的数据，1≤n≤1051 \le n \le {10}^5，1≤m≤5×1051 \le m \le 5 \times {10}^5。

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
int in[100020];
int n, m, x, y, cnt;
int dfn[100020];
int low[100020];
int stk[100020], ss;
int v[100020];
int r[100020], scc;
void tarjan(int x)
{
	dfn[x] = low[x] = ++cnt;
	stk[ss++] = x;
	v[x] = 1;
	for (int y: a[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (v[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		scc++;
		int u;
		do
		{
			u = stk[--ss];
			r[u] = scc;
			v[u] = 0;
		}
		while (u != x);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j: a[i])
		{
			if (r[i] != r[j])
			{
				in[r[j]]++;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= scc; i++)
	{
		if (!in[i])
		{
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

题解

P2272 [ZJOI2007]最大半连通子图

https://www.luogu.com.cn/problem/P2272

题目描述

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

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

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

输入格式

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

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

输出格式

应包含两行，第一行包含一个整数 KK，第二行包含整数 C mod XC\bmod X。

样例 #1

样例输入 #1
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
样例输出 #1
3
3

提示

对于 100%100\% 的数据，N≤105N\le 10^5，M≤106M\le 10^6，X≤108X\le 10^8。

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
vector<int> b[100020];
int n, m, mod, x, y, cnt;
int dfn[100020];
int low[100020];
int stk[100020], ss;
int c[100020];
int f[100020];
int g[100020];
int v[100020];
int r[100020], scc;
void tarjan(int x)
{
	dfn[x] = low[x] = ++cnt;
	stk[ss++] = x;
	v[x] = 1;
	for (int y: a[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (v[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		scc++;
		int u;
		do
		{
			u = stk[--ss];
			r[u] = scc;
			v[u] = 0;
		}
		while (u != x);
	}
}
int main()
{
	scanf("%d%d%d", &n, &m, &mod);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j: a[i])
		{
			if (r[i] != r[j])
			{
				b[r[i]].push_back(r[j]);
			}
		}
		c[r[i]]++;
	}
	int ansf = 0, ansg = 1;
	for (int i = 1; i <= scc; i++)
	{
		g[i] = 1;
		sort(b[i].begin(), b[i].end());
		b[i].resize(unique(b[i].begin(), b[i].end()) - b[i].begin());
		for (int j: b[i])
		{
			if (f[i] < f[j])
			{
				f[i] = f[j];
				g[i] = g[j];
			}
			else if (f[i] == f[j])
			{
				g[i] = (g[i] + g[j]) % mod;
			}
		}
		f[i] += c[i];
		if (ansf < f[i])
		{
			ansf = f[i];
			ansg = g[i];
		}
		else if (ansf == f[i])
		{
			ansg = (ansg + g[i]) % mod;
		}
	}
	printf("%d\n", ansf);
	printf("%d\n", ansg);
	return 0;
}

题解

P2656 采蘑菇

https://www.luogu.com.cn/problem/P2656

题目描述

小胖和 ZYR 要去 ESQMS 森林采蘑菇。

ESQMS 森林间有 NN 个小树丛，MM 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次，可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。

比如，一条路上有 44 个蘑菇，这条路的“恢复系数”为 0.70.7，则第一~四次经过这条路径所能采到的蘑菇数量分别为 4,2,1,04,2,1,0。

现在，小胖和 ZYR 从 SS 号小树丛出发，求他们最多能采到多少蘑菇。

输入格式

第一行两个整数，NN 和 MM。

第二行到第 M+1M+1 行，每行四个数，分别表示一条小路的起点，终点，初始蘑菇数，恢复系数。

第 M+2M+2 行，一个整数 SS。

输出格式

一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 (231−1)(2^{31}-1)。

样例 #1

样例输入 #1
3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1
样例输出 #1
8

提示

对于 30%30\% 的数据，N≤7N\le 7，M≤15M\le15

另有 30%30\% 的数据，满足所有“恢复系数”为 00。

对于 100%100\% 的数据，1≤N≤8×1041 \le N\le 8\times 10^4，1≤M≤2×1051\le M\le 2\times 10^5，0≤恢复系数≤0.80\le\text{恢复系数}\le 0.8 且最多有一位小数， 1≤S≤N1\le S\le N。

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
vector<pair<int, int> > b[100020];
int n, m, cnt;
int dfn[100020];
int low[100020];
int stk[100020], ss;
int sum[100020];
int f[100020];
int v[100020];
int r[100020], scc;
int x[200020];
int y[200020];
int w[200020];
double z[200020];
void tarjan(int x)
{
	dfn[x] = low[x] = ++cnt;
	stk[ss++] = x;
	v[x] = 1;
	for (int y: a[x])
	{
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (v[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		scc++;
		int u;
		do
		{
			u = stk[--ss];
			r[u] = scc;
			v[u] = 0;
		}
		while (u != x);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d%lf", &x[i], &y[i], &w[i], &z[i]);
		a[x[i]].push_back(y[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			tarjan(i);
		}
	}
	for (int i = 0; i < m; i++)
	{
		if (r[x[i]] != r[y[i]])
		{
			b[r[x[i]]].push_back(make_pair(r[y[i]], w[i]));
		}
		else
		{
			int t = w[i];
			while (t > 0)
			{
				sum[r[x[i]]] += t;
				t *= z[i];
			}
		}
	}
	for (int i = 1; i <= scc; i++)
	{
		for (pair<int, int> j: b[i])
		{
			f[i] = max(f[i], f[j.first] + j.second);
		}
		f[i] += sum[i];
	}
	int start;
	scanf("%d", &start);
	printf("%d\n", f[r[start]]);
	return 0;
}

题解

P6030 [SDOI2012]走迷宫

https://www.luogu.com.cn/problem/P6030

题目描述

Morenan 被困在了一个迷宫里。迷宫可以视为 nn 个点 mm 条边的有向图，其中 Morenan 处于起点 ss，迷宫的终点设为 tt。可惜的是，Morenan 非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样，Morenan 走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大。但你必须想方设法求出 Morenan 所走步数的期望值。

输入格式

第一行四个整数，n,m,s,tn,m,s,t。

接下来 mm 行，每行两个整数 u,vu, v ，表示有一条从 uu 到 vv 的边。

输出格式

一个浮点数，保留小数点后 33 位，为步数的期望值。若期望值为无穷大，则输出INF。

样例 #1

样例输入 #1
6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6
样例输出 #1
3.000

样例 #2

样例输入 #2
9 12 1 9
1 2
2 3
3 1
3 4
3 7
4 5
5 6
6 4
6 7
7 8
8 9
9 7
样例输出 #2
9.500

样例 #3

样例输入 #3
2 0 1 2
样例输出 #3
INF

提示

测试点 n≤n\leq m≤m\leq
1∼61\sim 6 1010 100100
7∼127\sim 12 200200 10410^4
13∼2013\sim 20 10410^4 10610^6

另外，均匀分布着 40%40\% 的数据，图中没有环，也没有自环。

对于 100%100\% 的数据，1≤n≤1041\leq n\leq 10^4，0≤m≤1060\leq m \leq 10^6，保证强连通分量的大小不超过 100\boldsymbol{100}。

参考代码

题解

f[i] 从i到终点，期望多少步

-f[i] + (枚举i能到的点j f[j] 求和) / i的度数 = +1
枚举i能到的点j 有两种
一种是和i同一个强连通分量的点，可以解方程得到
另一种是和i不在一个强连通分量的点，因为拓扑排序的缘故，一定可以在自己之前得到

  1. 强连通分量
    1. 定义
    2. 参考题目
      1. P1726 上白泽慧音
      2. P1262 间谍网络
      3. P2002 消息扩散
      4. P2272 [ZJOI2007]最大半连通子图
      5. P2656 采蘑菇
      6. P6030 [SDOI2012]走迷宫
≡