以前学的全都忘了orz
前置知识：深度优先搜索树
以v为结点，对每个点进行dfs遍历，所得到的搜索树，即为深度优先搜索树
易知，对每个点仅遍历一次，故我们在该深度优先搜索树中加入”回退边”，来表示该节点与已遍历到的节点之间亦存在边
故我们在该树中存在两种边，一种是实际遍历到的边，一种是没有使用的回退边
何为割点？
给定一个连通的无向图，其中任意一点被删除后，剩下的图仍连通，则称其为双连通图；若删除一些点后，剩下的图不连通，则称该点为割点or关节点
我们利用上述搜索树的想法，维护dfn[i]和low[i]两个数组，dfn表示该点被遍历到的次序(故用先序遍历)，而low表示该点搜索子树(包含本身、包含回退边)的dfn最小值(故用后序遍历)
对于割点，在搜索树中，除了根节点外，若一个节点v的子树中存在一个节点u，其low[u]>=dfn[v]，即u不存在指向v祖先的回退边，此时删除v，会使该节点与其他不再连通，故此时v为割点(根节点没有祖先，故特殊处理)
对于根节点，若其子树(在搜索树中两颗子树之间不相通)数量大于等于2，则此时删除根节点也会导致不连通，故根节点也为割点；否则根节点不是割点
给定有向图，强连通分量为一个点集，该点集中的点可以到达点集中的其他任意点(易知必定成环)
若整个图都为强连通分量，则称其为强连通图
故我们可以通过求强连通分量将有向有环图染色缩点，化为有向无环图
如何求？
Tarjan算法，以dfs为基础，由强连通分量必定成环的特性，维护两个数组，dfn[i]与low[i]，与一个栈stack，其中dfn为该点第一次被遍历到的时间次序，而low则是该点所能遍历到的点的dfn最小值，stack用来记录强连通分量中的点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35stack<int>s;
int dfn[200005],low[200005];//初始置为0
int col[200005];//用来染色
vector<int>g[200005];//存图
bool vis[200005];//表示点是否在栈中
int col_num=0,tot=0;
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s.push(x);
vis[x]=1;
for(auto e:g[x])
{
if(!dfn[e])
{
tarjan(e);
low[x]=min(low[x],low[e]);
}else if(vis[e])
{
low[x]=min(low[x],low[e]);//对回退边进行统计
}
}
if(dfn[x]==low[x])//本节点即为一个强连通分量的代表节点
{
col[x]=++col_num;
vis[x]=0;
while(s.top()!=x)//统计该分量内的点
{
vis[s.top()]=0;
col[s.top()]=col_num;
s.pop();
}
s.pop();
}
}Kosaraju算法，大致思路是将所有边反向，建一个反向图，对反向图进行dfs后得到dfs序，再对正向图根据dfs序列的反进行dfs，以消除单向边的影响
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34bool vis[200005];
int q[200005];
int n,tot=0;
int fa[200005]
vector<int> g1[200005],g2[200005];
void dfs1(int x)
{
vis[x]=1;
for(auto e:g[x])
{
if(!vis[e])
{
dfs1(e);
}
}
q[++tot]=x;
}
void dfs2(int x,int y)
{
vis[x]=0;
fa[x]=y;
for(auto e:g[x])
{
if(vis[e])
{
dfs2(e,y);
}
}
}
int main()
{
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
for(int i=n;i>=1;i--) if(vis[q[i]]) dfs2(q[i],q[i]);
}本文内容大部分参考来源：