题解 for Luogu P2661，P2746，P2812，P2194，P2169，P2835，P2002 以上题目都可以用 Tarjan 求强连通分量来做。
请正确使用文章目录和返回顶部功能。
P2661 信息传递
思路
这道题就是求图中所构成的最小环，这个环一定是强连通分量。 所以跑 Tarjan 求出最小的 SCC 大小（即分量内点的数量）即可。
要注意 SCC 大小为 1 时是不符合条件的，因为内部只有一个点，不能说它构成了环，要特判这种情况。
部分代码
（其他部分参考以前的 Tarjan 代码）
if (dfn[v] == low[v]) {
int u = sta.top(), siz = 0;
do {
siz++;
u = sta.top();
vis[u] = false;
sta.pop();
} while (v != u);
if (siz > 1) ans = min(ans, siz);
}P2746, P2812 校园网络
思路
这两道题是同一道题~~（双倍经验！）~~。 依然是缩点，根据 SCC 的性质。
第一问要求求出至少需要多少软件副本，只要统计入度为 0 的 SCC 个数即可， 这样可以保证每个学校都有软件副本。
第二问要求求出使得任意一个点能够到达其他所有点需要添加多少条边。 要达成这种情况，必须使只有入度为 0 的点只有一个才行，那么必须使其他入度为 0 的点至少入一条边才行。 那么应该把多出来的出度为 0 的点连到这些点上，这样可以使得边数最少，因为连城一个环的边数最少。 反过来想，对于每个出度为 0 的点，需要连一个出边，也是像这样。 所以最后统计入度为 0 的点与出度为 0 的点的最大值即可。
注意特判 SCC 数量为 1 的情况。此时只需一份软件副本且无需连边。
部分代码
//（主函数）
for (int i = 1; i <= cnt; i++)
if (color[from[i]] != color[to[i]])
out[color[from[i]]]++, in[color[to[i]]]++;
for (int i = 1; i <= sccnt; i++) {
if (!in[i]) innum++;
if (!out[i]) outnum++;
}
if (sccnt == 1) printf("1\n0\n");
else printf("%d\n%d\n", innum, max(innum, outnum));P2194 HXY 烧情侣
思路
依然是先缩点。统计每个 SCC 中的最小点权值，最小花费即为这些点权值之和。
第二问是典型的乘法原理。有多少个最小值就有多少种方法。由于这些方法是相互独立的，所以符合乘法原理。
部分代码
void tarjan() {
/*省略*/
if (dfn[v] == low[v]) {
sccnt++;
int u = sta.top();
do {
u = sta.top();
vis[u] = false;
sta.pop();
color[u] = sccnt;
mini[sccnt] = min(mini[sccnt], val[u]);
} while (v != u);
}
}
int main() {
/*省略*/
for (int i = 1; i <= sccnt; i++) ans1 += mini[i];
for (int i = 1; i <= n; i++)
if (val[i] == mini[color[i]]) minum[color[i]]++;
for (int i = 1; i <= sccnt; i++) ans2 = ans2 * minum[i] % MOD;
printf("%d %lld", ans1, ans2);
}P2169 正则表达式
思路
缩点 + SPFA（或其他最短路算法） 如果两个点在同一个 SCC 内，那么它们的边权值为 0。
部分代码
void spfa() {
/*省略*/
while (!que.empty()) {
/*省略*/
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (color[u] == color[v]) edge[i].cost = 0;
if (dis[v] > dis[u] + edge[i].cost) {
/*省略*/
}
}
}
}P2835 刻录光盘
思路
和校园网络的第一问一样，只需要统计入度为 0 的 SCC 的数目即可。
不过这道毒瘤题的第六个点居然卡快读，第一行明明输入了 61 而实际上只有 58 行
代码和校园网络基本一样，只需要改读入。
P2002 消息扩散
思路
依然是一道缩点 + 统计入度为 0 的 SCC 数量的题。
但是这道题需要注意的是存在重边和自环，所以不能单纯第从 1 到 n 去枚举每一个点的入度。 在读入时要把自环的情况去掉，这对入度不作出任何贡献。 在枚举时要枚举每一个点的出边所连点，保证重边的情况也能统计到。
部分代码
//(主函数)
for (int u = 1; u <= n; u++)
for (int i = head[u]; ~i; i = edge[i].next)
if (color[u] != color[edge[i].to])
in[color[edge[i].to]]++;
for (int i = 1; i <= sccnt; i++)
if (!in[i]) ans++;
printf("%d\n", ans);