Tarjan小分类
注：缩点是在求连通分量的基础上进行的优化，而割点与其他两个没有什么直接联系，但三种代码还是非常像的。
接下来正式进入Tarjan学习
1.Tarjan求连通分量
虽然但是……连通分量是什么呢……
以下摘自百度
无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。
啧……看不懂。
所以我们来翻译一下：
连通分量可以直观地理解为极大连通子图。（虽然我并不知道连通分量是不是就是极大连通子图）
如果这是个连通图，也就是说任意两点之间可以走到对方，那么，他有且仅有 它本身 这一个连通分量；
如果这是个非连通图，也就是说，有两点之间是不能互相走到的，这就会导致整张图分为了几个子图，在这几个子图内部，任意两点可以互相走到，那么，这几个子图均被称为连通分量。
更简单的说，就是一张图分为好几坨，每坨都是连通图，每坨有个共同的名字叫连通分量。
当然，如果这是个有向图，就要在前面加一个“强”字，毕竟人家作为有向图要两两互通也不容易。相应的，还有单向连通图和弱连通图，这里建议去百度一下……
举个栗子 （几乎是全网讲Tarjan的通用图）
图中，1,2,3,4,均能互相走到，但是，5无法走到1,2,3,4，6也无法走到1,2,3,4，所以1,2,3,4 这四个点为一坨，是一个连通分量。
5能走到6，但6走不到5，所以，5,6 两个人各自成家成一坨，分别为两个连通分量。
至此，第一个烦恼就被解决了……
接下来，看看我们可爱的Tarjan算法
注：本文图片均来自于@SHHHS
首先，我们需要引入两个可爱的数组：dfn和low
\(dfn[ ]\)：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据\(dfn[]\)来判断是否需要到过这个点。
\(low[ ]\)：该子树中，且当前仍在栈中的最小时间戳，也就是能到的最小的点（比较抽象，可以看看下面的图一起理解），\(low[ ]\)相等的点在同一强连通分量中。
- 在初始化时，\(dfn[]=low[]=++cnt\)，所以，当在走完所有支路回溯时，如果\(dfn[]==low[]\)，则当前栈中从当前点到栈顶的元素构成一个(强)连通分量。
由于这个图不一定是一个连通图，所以跑Tarjan时要枚举每个点，若\(dfn[ ] == 0\)，进行深搜。
然后对于搜到的点寻找与其有边相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则更新\(low[]\).
继续用上面那个栗子来展示Tarjan算法的过程：
第一遍搜到底，到再也没法搜为止，至此，5的支路走完。
回溯至3，到第二条支路，走到4。
走到6，6已经走过，不用再做；
回溯至4，到另一条支路，走到1，更新当前点的\(low[]\)值为1，至此4的支路全部走完。
回溯至3，至此，3的支路走完。
回溯至1，走第二条路，走到2，再走到4，4已经走过，退出。
回溯至1，至此，所有点走完。
连通分量也被找出来了~
让我们放出我们可爱的代码：
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,s,p,ct,cnt,sum;
struct node
{
int a,b,next;
}f[200005];
int g[50005];
int low[1000005],dfn[1000005];
bool usd[1000005];
int col[1000005];
stack<int>st;
void read(int &x)
{
x=0;int f=1;char ch=getchar();
while ((ch<'0')||('9'<ch))
{if (ch=='-') f=-1;ch=getchar();}
while (('0'<=ch)&&(ch<='9'))
{x=x*10+ch-'0';ch=getchar();}
}
void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10);putchar(x%10+'0');
}
void add(int a,int b)//挂链儿
{
f[++cnt].a=a;f[cnt].b=b;
f[cnt].next=g[a];g[a]=cnt;
}
void tarjan(int u)
{
dfn[u]=low[u]=++ct;
usd[u]=1;st.push(u);
for (int i=g[u];i;i=f[i].next)
{
int v=f[i].b;
if (!dfn[v])//如果这个点没做过，就来跑一跑
{
tarjan(v);
low[u]=min(low[v],low[u]);//更新你的low[]
}
else
{
if (usd[v])
low[u]=min(low[v],low[u]);//如果已经在栈中，成环，就需要更新一下
}
}
if (dfn[u]==low[u])//形成环，找到一个连通分量
{
int r;++sum;
do
{
r=st.top();st.pop();
usd[r]=0;col[r]=sum;//出栈后记得染色 ,不过这里就直接输出了
write(r),putchar(' ');
}while(r!=u);//全部出栈
putchar('\n');
}
}
int main()
{
read(n);read(m);
for (int i=1;i<=m;++i)
{
int a,b;
read(a);read(b);
add(a,b);
}
s=1;
for (int i=1;i<=n;++i)
if (!dfn[i]) tarjan(i);//如果没跑过，就跑一次Tarjan
return 0;
}
2.缩点（其实和上面的基本一样）
缩点，顾名思义，就是把一堆东西缩成一个点，就像物理中的质点一样，不用考虑内部。而这里的缩点，是把上面求出来的一坨一坨都缩成一个点一个点。
这里直接用的洛谷模板题P3387
大致题意，一个有向图，每个点有点权，每条边每个点可以重复走，权值只计算一次，求出最大权值和。
所以用一个spfa
这里也不多做阐述，实在不会去这里吧……
去完还不会这里……
还不会我也没办法了，这是我能力范围内最清晰的讲解了。毕竟我也是这里学的。
#include<bits/stdc++.h>
using namespace std;
int n,m,s,p,ct,cnt,sum,ans;
struct node
{
int a,b,next;
}f[200005],f2[200005];
int g[50005],g2[50005];
int c[500005],w[500005];
int low[1000005],dfn[1000005];
int col[1000005],dis[1000005];
bool usd[1000005];
queue<int>q;
stack<int>st;
void read(int &x)
{
x=0;int f=1;char ch=getchar();
while ((ch<'0')||('9'<ch))
{if (ch=='-') f=-1;ch=getchar();}
while (('0'<=ch)&&(ch<='9'))
{x=x*10+ch-'0';ch=getchar();}
}
void add(int a,int b)
{
f[++cnt].a=a;f[cnt].b=b;
f[cnt].next=g[a];g[a]=cnt;
}
void add2(int a,int b)
{
f2[++cnt].a=a;f2[cnt].b=b;
f2[cnt].next=g2[a];g2[a]=cnt;
}
void tarjan(int u)
{
dfn[u]=low[u]=++ct;
usd[u]=1;st.push(u);
for (int i=g[u];i;i=f[i].next)
{
int v=f[i].b;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[v],low[u]);
}
else
{
if (usd[v])
low[u]=min(low[v],low[u]);
}
}
if (dfn[u]==low[u])
{
int r;++sum;
do
{
r=st.top();st.pop();
usd[r]=0;col[r]=sum;
}while(r!=u);
}
}
int spfa(int s)//以s为起点，spfa模板，不会的自己想办法吧。。。
{
queue<int>q;
memset(dis,0,sizeof(dis));
q.push(col[s]);
usd[col[s]]=1;
dis[col[s]]=w[col[s]];
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=g2[u];i;i=f2[i].next)
{
int v=f2[i].b;
if (dis[u]+w[v]>dis[v])//这可不是真的最短路啊，这里求的是最长路
{
dis[v]=dis[u]+w[v];
if (!usd[v])
{
q.push(v);
usd[v]=1;
}
}
}
usd[u]=0;
}
int as=0;
for (int i=1;i<=sum;i++)
as=max(as,dis[i]);
return as;
}
int main()
{
read(n);read(m);
for (int i=1;i<=n;++i) read(c[i]);
for (int i=1;i<=m;++i)
{
int a,b;
read(a);read(b);
add(a,b);
}
s=1;
for (int i=1;i<=n;++i)
if (!dfn[i]) tarjan(i);
cnt=0;
for (int i=1;i<=n;++i)
{
for (int j=g[i];j;j=f[j].next)
{
int v=f[j].b;
if (col[v]!=col[i])//不属于同一块，但是他们之间有边，所以缩点时也会有边
add2(col[i],col[v]);
}
}
for (int i=1;i<=n;i++)
w[col[i]]+=c[i];
for (int i=1;i<=n;i++) ans=max(ans,spfa(i));
cout<<ans;
return 0;
}
3.割点
割点，也挺好理解的，就是把一个点拿掉，一张连通图就变成了非连通图。
如果是根节点，那么如果它有两个以上的边，它就是一个割点；
如果是非根节点，那么当一条\(u->v\)的边\(dfn[v]<dfn[u]\)，它就是一个割点。
但是！！这玩仍交上去是错的！！所以，我去翻了翻题解……
@Michael_Li：根据许多大佬的观点，我想提出自己的一点看法，在求强连通分量时，如果v已经在栈中，那么说明u，v一定在同一个强连通分量中，所以到最后low[u]=low[v]是必然的，提前更新也不会有问题，但是在求割点时，low的定义有了小小的变化，不再是最早能追溯到的祖先，（因为是个无向图）没有意义，应该是最早能绕到的割点，为什么用绕到，是因为是无向边，所以有另一条路可以走，如果把dfn[v]改掉就会上翻过头，可能翻进另一个环中，所以wa掉，仅是本人的一些个人看法，不知道讲的对不对，请各位指教。
具体请参考这里
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct node
{
int a,b,next;
}f[maxn];
int n,m,cnt,t,g[maxn],ans[maxn];
int dfn[maxn],low[maxn],fa[maxn];
bool usd[2*maxn],used[2*maxn];
void read(int &x)
{
x=0;bool f=0;char ch;ch=getchar();
while (('0'>ch)||(ch>'9'))
{if (ch=='-') f=1;ch=getchar();}
while (('0'<=ch)&&(ch<='9'))
{x=x*10+ch-'0';ch=getchar();}
if (f) x=-x;
}
void add(int a,int b)
{
f[++cnt].a=a;f[cnt].b=b;
f[cnt].next=g[a];g[a]=cnt;
}
void tarjan(int u)
{
int sum=0;usd[u]=1;
dfn[u]=low[u]=++cnt;
for (int i=g[u];i;i=f[i].next)
{
int v=f[i].b;
if (!usd[v])
{
fa[v]=u;//记录父节点，来判断起始点，毕竟后面还要往回找补找补
sum++;//sum记录连接的还没有做过的节点数，主要应付那个臭屁的根节点
tarjan(v);
low[u]=min(low[u],low[v]);
if ((fa[u]!=u)&&(low[v]>=dfn[u]))
{if (!used[u]) ++t,used[u]=1;}//不然会重复的宝儿，可以用set，但是我不会
//不能算上臭屁的根节点
}
else low[u]=min(low[u],dfn[v]); //**注意！！这里是dfn[v]和low[u]在比较
}
if ((fa[u]==u)&&(sum>=2)) {if (!used[u]) ++t,used[u]=1;}
}
int main()
{
read(n);read(m);
for (int i=1;i<=m;++i)
{
int x,y;
read(x);read(y);
add(x,y);add(y,x);
}
cnt=0;
for (int i=1;i<=n;++i)
if (!usd[i])
{
fa[i]=i;
tarjan(i);
}
cout<<t<<endl;
for (int i=1;i<=n;++i)
if (used[i]) cout<<i<<' ';
return 0;
}