算法学自 BYVoid
https://www.byvoid.com/zhs/blog/scc-tarjan/
这个写得很清楚了
当然 你可能不这么认为
而且 如果是让我 一开始就从这个博客 学 tarjan 缩点
估计我也会觉得 很难懂
我猜是 博客看多了 有了些基础
在看这一篇的时候懂了
就觉得 是这篇比较好懂
（事实上人家本来写得就可以嘛）
我想到了 班主任的一句话
量的积累 才有质的变化
tarjan 缩点 求 scc（strongly connected components）
有向图 强连通分量
首先 给自己 刷个广告
tarjan 是基于 dfs树 的算法
我觉得 dfs树 上的一些 术语有必要知道 一下
所以， 看我 博客
还有， 就是 ，两个数组 dfn[] ， low[]
分别为 i的时间戳 ， i能最早追溯到的时间戳
这个比较难理解
但非常重要
因为 tarjan 发明的 求 割点、割边 的算法
也要活用到 这两个数组
（其实不用怕 tarjan ，这不过是个帅哥 的名字 罢了）
说说我的个人理解
dfn [ i ] 是程序第几次 dfs 到 节点 i
所以起名叫 dfn ( dfs 的 第 n 次执行 ，n ∈ [ 1 , MAXN ] );
low [ i ] 是 dfs 过程中 有时会
遇到回到 之前 节点的 路径 ( 之前 是指先前 dfs 到 的 点 )
那么 节点 i 就能 沿着 这条路 返回 之前的点
low [ i ] 就是 i { [ 能返回的 ( dfn值最小的 ) 点 ] 的dfn值 }
额 。理不理解都往下看吧 毕竟 量的积累 还是很有必要的
每次dfs(点u){
dfn[u] = 进入 dfs() 函数的次数 （自己定义一个时间戳记录 如 timee）
枚举与其相邻的点v{
如果 没有 访问过点v { ( 就是dfs树上的树边 )
dfs(v);
如果 v 能追溯 到 比“u 追溯到的最早的点” 更早的点；
那么 u 就能 通过 v 来追溯到 那个点；
low[u]=min(low[u],low[v]);
}
如果 访问过点v && v在栈中
low[u]=min(low[u],dfn[v]);
}
缩点
}
两个例题
输出要求不同，
笔者建议 独立体会
下面的 代码 大同小异
1
#include<iostream>
#include<stack>
#include <cstring>
using namespace std;
int m,ans,bbk[],bk,b[],head[],cnt,dfn[],low[],n;
stack<int>zz;
bool ru[];
struct aa{
int to,next;
}e[];
void add(int x, int y)
{
e[cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt++;
}/*void add(int from,int to){
e[++cnt]=(aa){to,head[from]};
head[from]=cnt;
}*/
void dfs(int k){
dfn[k]=low[k]= ++cnt;
b[k]=;
zz.push(k);
int j;
for(int i=head[k];i!=-;i=e[i].next){
j=e[i].to;
if(!dfn[j]){
dfs(j);
low[k]=min(low[k],low[j]);
}
else if(b[j]&&dfn[j]<low[k])low[k]=dfn[j];
}
if(dfn[k]==low[k]){
bk++;
do{
j=zz.top();
zz.pop();
b[j]=;
bbk[j]=bk;
}while(j!=k);
}
}
int main(){
cin>>n;
memset(head, -, sizeof(head));
for(int x,i=;i<=n;i++){
cin>>x;
while(x){
add(i,x);
cin>>x;
}
}
cnt=;
for(int i=;i<=n;i++)
if(!dfn[i])
dfs(i);
for(int i=;i<=n;i++)
for(int y,j=head[i];j!=-;j=e[j].next){
y=e[j].to;
if(bbk[y]!=bbk[i])ru[bbk[y]]=;
}
for(int i=;i<=bk;i++)
if(!ru[i])
ans++;
cout<<ans;
return ;
}
2
#include<iostream>
#include<stack>
using namespace std;
int m,ans,bbk[],bk,b[],head[],cnt,dfn[],low[],n;
stack<int>zz;
struct aa{
int to,next;
}e[];
void add(int from,int to){
e[++cnt]=(aa){to,head[from]};
head[from]=cnt;
}
void dfs(int k){
dfn[k]=low[k]= ++cnt;
b[k]=;
zz.push(k);
int j;
for(int i=head[k];i;i=e[i].next){
j=e[i].to;
if(!dfn[j]){
dfs(j);
low[k]=min(low[k],low[j]);
}
else if(b[j]&&dfn[j]<low[k])low[k]=dfn[j];
}
if(dfn[k]==low[k]){
bk++;
do{
j=zz.top();
zz.pop();
b[j]=;
bbk[bk]++;
}while(j!=k);
}
}
int main(){
cin>>n>>m;
for(int x,y,i=;i<=m;i++){
cin>>x>>y;
add(x,y);
}
cnt=;
for(int i=;i<=n;i++)
if(!dfn[i])
dfs(i);
for(int i=;i<=bk;i++)
if(bbk[i]>)
ans++;
cout<<ans;
return ;
}
