tarjan算法求强连通分量详解(避免误区)

trajan算法求强连通分量

这是一个很好的算法OwO
我们来自己画个图手模一遍，差不多就可以理解了
网上很多将tarjan的，因为图太简单，特殊情况太少，所以会出现许许多多的误区，希望看了这篇啰里巴嗦的博客能对你有所帮助OwO

---

我本人一开始死都不明白那个dfn（时间戳）又什么用QAQ后来在fyy大佬%%%的帮助下，发现dfn是个很有用的东西！！！！！！
不多说了，直接上图

输入

15 23
1 2
4 6
7 13
13 14
10 15
2 3
2 4
5 9
1 8
15 1
8 10
13 3
14 10
3 4
9 4
6 12
3 7
11 3
10 15
8 2
14 3
12 4
4 5

终于拟完一组数据了~~~~
接着开始手模OwO
先初始化，每个点的vis均赋值为0；
接着每个点被访问时均先进栈，访问完毕后出栈。
scc数组记录每个点所从属的强连通分量的编号，初始全为0

从一号点开始dfs，标记dfn[1]=1,low[1]=1,vis[1]=1;
继续dfs，标记dfn[2]=2,low[2]=2,vis[2]=1;
继续dfs，标记dfn[4]=3,low[4]=3,vis[3]=1;
继续dfs，标记dfn[5]=4,low[5]=4,vis[4]=1;
继续dfs，标记dfn[9]=5,low[9]=5,vis[5]=1;
此时栈中元素为：1，2，4，5，9
到这里还是比较和蔼的。。所以一张图解决

然后就出现问题了,4号节点已经被访问（vis[4]=1），要是不做处理的话就会出现死循环。
此时由于scc[4]=0（由于4号点的强连通分量编号还不知道，那么显然它还不属于任何一个强连通分量，于是乎，9->4是一条返祖边而非横叉边）,那么我们可以判断出，我们已经找出了一条返祖边，那么我们就不从4号节点搜索了，直接返回，并将low[9]赋值为low[4]

此时dfn[9]!=low[9]，即无法构成强连通分量，回溯。
这时候，我们又发现low[5]>low[9]（这里面就涉及到dfn的用处了，我本来是打算直接用点的序号来代替dfn的，<似乎还可以在最后处理的时候当并查集来用，其实不然>，但是要是代替了的话，将无法在O（1）的时间内判断出5和9是否在同一个强连通分量里了，再%%%fyy大佬）,那么，我们就将low[5]赋值为low[9]因为这很明显，5和9在同一个强连通分量里。但我们此时先不做太大的处理，具体处理方式后面会讲。
另外一棵子树同理。
此时dfn[6]=6,low[6]=6,vis[6]=1;
dfn[12]=7,low[12]=7,vis[12]=1;
栈中元素为：1，2，4，5，9，6，12

回溯到4号点时，我们发现dfn[4]==low[4],那么，我们即可判断栈中4号点之后的所有节点均在同一个强连通分量里（如果存在只有入度，没有出度的点，那么这个点的dfn值一定等于low值，所以改点已经出栈），所以我们将计数器sccn++，并同时进行栈的pop操作，之道把4号点pop出来为止，并且将pop出来的点的scc均附为当前的sccn值。
即：
scc[12]=sccn;12出栈
scc[6]=sccn;6出栈
scc[9]=sccn;9出栈
scc[5]=sccn;5出栈
scc[4]=sccn;4出栈
于是我们得到了第一坨强连通分量{4，5，9，6，12}

继续dfs，dfn[3]=8,low[3]=8,vis[3]=1;
下一个节点是4号（别问我为什么还是4号，我也不知道）
发现vis[4]!=0,并且scc[4]!=0;于是我们就可以知道这是一条爱理不理的横叉边，假装它不存在就行了，继续。
继续dfs，dfn[7]=9,low[7]=9,vis[7]=1;
然后你会发现，7号点马上又回到了3号点，用前面的处理方法，将7号点的low值附为3号点的low值，然而往后分析，你会发现13号，14号，11号节点都有一条指向3号点的返祖边

---

这种东西是专门卡那些没把tarjan理解透的代码的，也就是我一开始的一个误区：每次找到返祖边就做一遍并查集操作，遇到这种东西，立刻被卡到爆炸，T到飞起，每次都傻傻的取更新一遍
然而真正的tarjan才没那么脆弱，它每次处理时间为O（1），当找到强连通分量时再来更新就快得多，反而减少了不必要的更新次数。
（好像扯得有点远了=。=）(反正我知道你们这段没看懂，别装作看懂了的样子OwO)

---

此时栈内元素为：1，2，3，7，13，14，11

继续回溯，到3号点时，dfn[3]==low[3]，再次出栈操作
sccn++
scc[11]=sccn;11出栈
scc[14]=sccn;14出栈
scc[13]=sccn;13出栈
scc[7]=sccn;7出栈
scc[3]=sccn;3出栈
于是我们得到了强连通分量{3，7，13，14，11}

回溯到2号节点，因为dfn[2]==low[2]，所以2是一个强连通分量
sccn++;
scc[2]=sccn;2出栈

回溯到1号节点，
继续dfs，标记dfn[8]=13,low[8]=13,vis[8]=1;
继续dfs，标记dfn[10]=14,low[10]=14,vis[10]=1;
继续dfs，标记dfn[15]=15,low[15]=15,vis[15]=1;
此时栈内元素为：1，8，10，15

继续dfs，又到了1号节点，找到一条15->1的返祖边，将low[15]附为low[1]，回溯
又low[10]>low[15]于是low[10]=low[15];
又low[8]>low[10]于是low[8]=low[10];
回溯到1号节点，没有另外的边了，放心，还没完，最后一步出栈操作！！
sccn++
scc[15]=sccn;15出栈
scc[10]=sccn;10出栈
scc[8]=sccn;8出栈
scc[1]=sccn;1出栈
于是我们得到了强连通分量{1，8，10，15}

大功告成！！！！！！！！！！！！！

下面贴代码

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int w,to,next;
}edge[200001];
queue <int> q;
stack <int> s;
int n,m,i,u,v,w,cnt,num,sccn;
int head[200001],low[200001],dfn[200001],scc[200001],d[200001];
bool vis[200001],inq[200001];
void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int x)
{
    int i;
    low[x]=dfn[x]=++num;//num必须为全局变量，代表当前访问的节点序号（时间戳）
    s.push(x);
    vis[x]=1;
    for (i=head[x];~i;i=edge[i].next)
        if (!vis[edge[i].to])//判断是否访问过（排除横叉边和返祖边）
        {
            dfs(edge[i].to);
            low[x]=min(low[x],low[edge[i].to]);
        }
        else
            if (!scc[edge[i].to])//若为返祖边
                low[x]=min(low[x],low[edge[i].to]);
    if (dfn[x]==low[x])//出栈操作
    {
        sccn++;
        int t;
        while (1)
        {
            t=s.top();
            s.pop();
            scc[t]=sccn;
            if (t==x) break;
        }
    }
}
void tarjan()
{
    int i;
    sccn=num=0;
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(scc,0,sizeof(scc));
    for (i=1;i<=n;i++)//此处为了防止整个图非联通，就对整个图进行tarjan
        if (!vis[i]) dfs(i);
}
int main()
{
    cin >> n >> m;
    cnt=0;
    memset(head,-1,sizeof(head));
    for (;cnt<m;)
    {
        cin >> u >> v;
        add(u,v);
    }
    tarjan();
    for (i=1;i<=n;i++) cout <<  << ' ';
}