强连通
强连通：有向图 \(G\) 中每个点中可互相到达。
强连通分量：极大的强连通。（最大可能的）
求强连通分量
先跑出图的 DFS 搜索树（黑边）。
一个结论：一个强连通分量 一定在该强连通分量中的第一个被访问的点 的子树内。
设根为 \(u\)，考虑若存在一个点 \(v\) 不在 \(u\) 子树中则一定存在一条边离开 \(u\) 子树，只可能是返祖/横叉边，显然指向的点已经被标记过了。
Tarjan
一般都用这个。
记 \(dfn(u),low(u)\)，后者表示 \(u\) 子树内可以回溯到的节点的 \(dfn\) 最小值（通过走非树边或者 DFS 回溯）。
记一个栈 \(stk\) 表示当前搜索到的节点，对于一个节点 \(v\)：
- \(v\) 未被访问：先算 \(v\) 的答案，再用 \(low(v)\) 更新 \(low(u)\)；
- \(v\) 访问过，且在栈中：用 \(dfn(v)\) 更新 \(low(u)\)；
- \(v\) 访问过，不在栈中：\(v\) 所在连通分量已被处理完。不做操作。
最后只有满足 \(dfn(u)=low(u)\) 的 \(u\) 才能作为结论中的点，据此确定一个强连通分量 \(G=\braket{stk,\cdot}\)。
时间复杂度 \(O(n+m)\)。非常优秀。
int stk[maxn],top;
int dfn[maxn],dfncnt;
int low[maxn];
bool ins[maxn];
int scc[maxn],scccnt;
void tarjan(int u){
dfn[u]=low[u]=++dfncnt;
stk[++top]=u; ins[u]=1;
for(int v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(ins[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scccnt++;
while(stk[top]!=u){
scc[stk[top]]=scccnt;
ins[stk[top]]=0;
top--;
}
scc[stk[top]]=scccnt;
ins[stk[top]]=0;
top--;
}
}
Kosaraju
黑科技吧。实现非常简单：DFS，以后序遍历（即回溯时编号，相当于反 \(dfn\) 满足 \(rdfn(u)>rdfn(v)(v\in subtree(u))\)）标号，在反图上从编号最大的点 DFS，所有遍历到的点即为一个强连通分量。？？？有点玄幻但的确是对的，马良极小。同样时间复杂度 \(O(n+m)\)。
int scc[maxn],scccnt;
int rdfn[maxn],dfncnt;
bool vis[maxn];
void dfs1(int u){
vis[u]=1;
for(int v:e[u])
if(!vis[v]) dfs1(v);
rdfn[++dfncnt]=u;
}
void dfs2(int u,int col){
scc[u]=col;
for(int v:re[u])
if(!scc[v]) dfs2(v);
}
void Kosaraju(){
for(int i=1;i<=n;i++)
if(!vis[i]) dfs1(i);
for(int i=n;i>=1;i--)
if(!scc[i]) dfs2(rdfn[i],++scccnt);
}
例题：[USACO03FALL / HAOI2006] 受欢迎的牛 G
每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
先缩点，然后找 DAG 上出边为 0 的点，如果不唯一就无解，否则即为那个点包含的连通分量大小。
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+3;
int n,m;
vector<int>e[maxn];
int stk[maxn],top;
int dfn[maxn],dfncnt,low[maxn];
int scc[maxn],scccnt;
bool ins[maxn];
int out[maxn],siz[maxn];
void tarjan(int u){
dfn[u]=low[u]=++dfncnt;
stk[++top]=u; ins[u]=1;
for(int v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(ins[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scccnt++;
while(stk[top]!=u){
scc[stk[top]]=scccnt;
ins[stk[top]]=0;
top--;
siz[scccnt]++;
}
scc[stk[top]]=scccnt;
ins[stk[top]]=0;
top--;
siz[scccnt]++;
}
}
signed main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e[u].emplace_back(v);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++){
for(int j:e[i]){
if(scc[i]!=scc[j]){
out[scc[i]]++;
}
}
}
int oucnt=0,id=0;
for(int i=1;i<=scccnt;i++){
if(out[i]==0) oucnt++,id=i;
}
if(oucnt>1){
cout<<0;
}else{
cout<<siz[id];
}
return 0;
}