\(Tarjan\)的学习笔记
一，\(tarjan\)概述：
（1）定义：
$~~~~~~~~$$tarjan$是基于深度优先搜索的一种算法，求解图的连通性等问题，巧妙地利用了对图进行深搜时产生的搜索树上的边。
（2）\(tarjan\)中的几种边：
\(~~~~~~~~\)树边：父亲与孩子的边。
\(~~~~~~~~\)前向边：祖先到孩子的边（树边属于特殊的前向边）。
\(~~~~~~~~\)后向边：孩子到祖先的边（与前向边相反）。
\(~~~~~~~~\)横叉边：这种边只有在有向图时才有，两个在搜索树上无祖宗、子孙关系的点之间的边。
\(~~~~~~~~\)在\(tarjan\)中，我们只关心树边和后向边。
二，\(tarjan\)应用一：求解有向图的强联通分量（\(SCC\)）（然后可以缩点）
（1）有向图的强联通分量（\(SCC\)）的定义：
\(~~~~~~~~\)在有向图中，如果两个顶点\(u\)，\(v\)存在\(u→v\)和\(v→u\)，那么则称\(u\)，\(v\)强连通。
\(~~~~~~~~\)如果有向图的任意两个顶点都强连通，则称为强连通图。
\(~~~~~~~~\)有向非强连通图的极大强连通子图，称为强连通分量。
（2）算法思路：
\(~~~~~~~~\)求解有向图的强联通分量时，最重要的是后向边，因为如果存在后向边\(u→v\)（根据定义，此时一定有\(v→u\)，为树枝边构成），那么\(u\)、\(v\)一定在同一个强连通分量中，那么，如何求解一条边是否为后向边呢？
\(~~~~~~~~\)首先，我们定义一个数组\(dfn\)，表示第\(u\)个节点是第几个被遍历到的（即时间戳）。
\(~~~~~~~~\)接着，我们可以定义一个栈\(s\)，其中的元素为当前搜索树上的点，那么如果存在一条后向边\(u→v\)，那么此时\(v\)一定在栈中。
\(~~~~~~~~\)于是我们再定义一个\(vis\)数组，就可以轻松找到\(v\)是否在栈里面了（入栈时\(vis\)变为\(1\)，出栈时\(vis\)变为\(0\)），这样子我们就可以找到两个点是否为强联通的了。
\(~~~~~~~~\)那么，怎么把一个\(SCC\)的所有点都找出来呢？
\(~~~~~~~~\)我们可以定义一个新的数组，\(low\)。\(low[u]\)表示从\(u\)出发最多只通过一条后向边能回溯到最小的\(dfn\)值。（注意，是从\(u\)出发，也就是说是从\(u\)以及它的子树回溯的最早的\(dfn\)值）
\(~~~~~~~~\)显然，若\(u→v\)是一个后向边，那么\(v\)是\(u\)在搜索树上的祖先，那么，\(low[u]=min(low[u],dfn[v])\)。而对于\(v→u\)路径上的每一个节点\(w\)，\(w\)和\(v\)、\(u\)属于同一个\(SCC\)，那么\(low[w]=min(low[w],dfn[v])\)。
\(~~~~~~~~\)那么，怎么用代码实现以上的步骤，对\(low\)数组进行更新呢？
\(~~~~~~~~\)我们可以在\(dfs\)内进行回溯时，判断一下当前搜索的节点\(u\)能到达的节点\(v\)中，是否有\(v\)也在栈中，如果在，那么对\(low\)数组进行更新，即\(low[u] = min(low[u], dfn[v])\)（此时\(u→v\)为后向边）。
\(~~~~~~~~\)另外，如果\(u→v\)为一条树边，那么\(low[u]=min(low[u],low[v])\)。
\(~~~~~~~~\)而在\(u\)所有的子树搜索完后，若\(low[u]\)依旧等于\(dfn[u]\)，则意味着节点\(u\)为它所在的\(SCC\)中第一个搜索到的节点，它无法回溯到\(dfn\)值比它小的节点，那么此时在栈中比\(u\)先出栈的元素一定就是和\(u\)在同一\(SCC\)中的。
\(~~~~~~~~\)那么，将栈中的比\(u\)先出栈的元素和\(u\)依次出栈，再用一个数组\(color\)对其进行标记（表示同属一个\(SCC\)），即可。
\(~~~~~~~~\)如果要进行缩点的话，那么所有\(color\)数组值一样的点可以看作一个大点，缩点后可以重新建图，或进行其他操作。
\(~~~~~~~~\)时间复杂度：\(O(N+M)\)，每个点出栈一次，进栈一次，每条边被访问一次。
（3）代码+注释：
#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
stack<int> s;
int dfn[N],low[N],head[N],f[N];
bool vis[N];
int color[N];
int tot,at,sum;
struct node{
int to,nt;
}a[M];
int n,m;
void add(int x,int y){
a[++at].to=y,a[at].nt=head[x],head[x]=at;
}
void tarjan(int u){
dfn[u]=low[u]=++tot;
vis[u]=1;
s.push(u);
for(int i=head[u];i;i=a[i].nt){
int v=a[i].to;
if(!dfn[v]){//树边
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){//后向边
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])//u为它所在的SCC中第一个搜索到的节点
{
sum++;
while(1){
int now=s.top();
s.pop();
vis[now]=0;
color[now]=sum;
if(now==u) break;
}//依次出栈，进行标记
}
}
int main(){
int x,y;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++){//如果当前节点未被搜索，则从此节点开始搜索
if (!dfn[i])tarjan(i);
}
return 0;
}
三，\(tarjan\)应用二：求解无向图的割点
（1）无向图的割点的定义：
\(~~~~~~~~\)若删除一个点（以及和它关联的边）后，原先的图分裂成两个及以上的不相连的图，则称那个点为割点。
（2）算法思路：
\(~~~~~~~~\)首先，我们思考一下，在搜索树上，一个点满足什么条件的时为割点？
\(~~~~~~~~\)①如果这个点为搜索树的根节点，那么若有两个及以上的子树无法到达除这个点外的点，那么把这个点删掉后，就会产生多个不相连的图。
\(~~~~~~~~\)②如果这个点不为搜索树的根节点，那么只要有一个子树无法到达除这个点外的点，那么把这个点删掉后，就会产生不相连的图。
\(~~~~~~~~\)也就是说，在进行搜索时，如果有\(u→v\)，并且\(v\)没有被搜索过，那么对\(v\)进行搜索。
\(~~~~~~~~\)回溯后，若\(low[v]<=dfn[u]\)，那么就代表节点\(v\)为根节点的搜索树上的所有点都无法回溯到时间戳比\(u\)跟小的点，则代表删除\(u\)后，这个子树间不能同除了\(u\)和这个子树上的点以外的点相连，若符合上述条件，则\(u\)为割点。
\(~~~~~~~~\)那么，具体的\(tarjan\)代码只需要在求\(SCC\)的代码上进行一些小修改即可
\(~~~~~~~~\)因为我们只关心一个点能回溯到的\(dfn\)的最小值，那么在搜索到\(u\)时，若存在\(u→v\)，且\(v\)没有被搜索过，那么就按照上文说的进行，否则则对\(low[u]\)值进行更新：\(low[u]=min(low[u],dfn[v])\)。
（3）代码+注释：
#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
int to,nt;
}a[M*2];
int head[N],at;
void add(int x,int y){
a[++at].to=y,a[at].nt=head[x],head[x]=at;
}
int dfn[N],low[N];
int num=0;
int root;
bool vis[N];
void tarjan(int u){
dfn[u]=low[u]=++num;
int v;
int flag=0;
for(int i=head[u];i;i=a[i].nt){
v=a[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
flag++;
if(u!=root||flag>=2) vis[u]=1;//判断是否符合条件
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
root=i;
tarjan(i);
}
}
return 0;
}
四，\(tarjan\)应用三：求解无向图的割边（桥）
（1）无向图的割边（桥）的定义：
\(~~~~~~~~\)若删除这条边后，原先的图分裂成两个及以上的不相连的图，则称这条边为割边（也称为桥）。
（2）算法思路：
\(~~~~~~~~\)首先，我们思考一下，在搜索树上，一个点满足什么条件的时为桥？
\(~~~~~~~~\)其实和割点需要满足的条件差不多，首先，一个桥在搜索树上一定是一条树边，不然的话割掉它一定不会对图的连通性产生影响。
\(~~~~~~~~\)但是，显然的是，肯定不是所有树边都为桥，只有在\(u→v\)，并且\(low[v]<dfn[u]\)时才成立，因为这样的话，在搜索树上，以\(v\)为根的子树能通过一条后向边回溯到的点就是在这棵子树上的，把这条边删除后它们就独立出来了。（注意，是\(<\)，而不是\(<=\)，因为我们删除的是边）
\(~~~~~~~~\)不过需要注意的是，因为是无向图，但我们采用链式前向星存图的时候一条边是存为两条有向边的，所以有可能会产生将走过的树边变为后向边情况，这样子就无法求解了。
\(~~~~~~~~\)不过由于存图相同的边是挨着的，且下标是一奇一偶，因此在使用\(v\)数组标记割边时，我们应该标记\(i\)和\(i\wedge1\)（因为奇数异或\(1\)为那个数\(+1\)，偶数为那个数\(-1\)），这样也可以避免把重边一刀切的情况。
\(~~~~~~~~\)同理，在走后向边时，也要判断一下，不是的话再更新\(low\)数组，否则则是在走做过的边。所以在\(tarjan\)时还要传一个参，表示它是由经过条边达到的，而在初始调用时则传参\(0\)，所以储存图的链表数组下标从\(2\)开始。（\(0\wedge1=1\)）
（3）代码+注释：
#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
int to,nt;
}a[M*2];
int head[N],at=1;//从1开始
void add(int x,int y){
a[++at].to=y,a[at].nt=head[x],head[x]=at;
}
bool vis[N];
int dfn[N],low[N];
int num=0;
void tarjan(int x,int k){
dfn[x]=low[x]=++num;
int y;
for(int i=head[x];i;i=a[i].nt){
y=a[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
vis[i]=vis[i^1]=1;
}
}
else if(i!=(k^1)) low[x]=min(low[x],dfn[y]);//判断是否走过
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
return 0;
}
五，\(tarjan\)应用四：求解无向图的点双连通分量（\(v-DCC\)）（然后可以缩点）
（1）无向图的点双连通分量（\(v-DCC\)）的定义：
\(~~~~~~~~\)若一个无向图不存在割点，称它为“点双连通图”，即删除任意一个点都连通。
\(~~~~~~~~\)无向图的极大点双连通子图称为“点双连通分量”，简称\(v-DCC\)。
（2）算法思路：
\(~~~~~~~~\)我们可以在求解割点的时候，同时求解点双连通分量（\(v-DCC\)），而过程基本同求解割点时一致，不过要注意的是，割点同时属于多个\(v-DCC\)。
\(~~~~~~~~~\)我们同求解\(SCC\)时一样，维护一个栈，在第一次访问节点\(u\)时，将其入栈。
\(~~~~~~~~~\)在判定割点时，若有\(u→v\)，使得\(u\)为割点，从则栈顶不断弹出节点，直至\(u\)在栈中的上一个节点，也就是\(v\)被弹出，（割点同时属于多个\(v-DCC\)，不用弹出）而弹出的所有节点与节点\(u\)一起构成一个点双连通分量。
\(~~~~~~~~\)不过，同求割点不同的是，求解只要\(v-DCC\)时，只要是满足了\(dfn[u]<=low[v]\)，就代表找到了一个\(v-DCC\)。为什么呢？
\(~~~~~~~~\)首先，求割点时的特判是针对\(u\)为根节点的情况的，那么我们分类讨论一下：①在搜索时，只有一次满足了这个条件，那么代表此时搜索树上的节点同属一个\(v-DCC\)。②不止一次满足了，那么\(u\)就是割点，那么此时访问到的节点就是同属一个\(v-DCC\)的。
\(~~~~~~~~\)注意，如果\(u\)不与任何点相连，那么它独属于一个\(v-DCC\)，在\(tarjan\)开始时特判即可。
\(~~~~~~~~\)最后，如果要进行缩点的话，我们将同属一个\(v-DCC\)的点加入同一个\(vector\)数组中，即可。
（3）代码+注释：
#include<bits/stdc++.h>
using namespace std;
const int N=10000+9,M=10000+9;
int n,m;
struct node{
int to,nt;
}a[M*2];
int head[N],at;
inline void add(int x,int y){
a[++at].nt=head[x],head[x]=at,a[at].to=y;
}
int dfn[N],low[N];
vector<int> b[N];//储存同属一个v-DCC的点
stack<int> q;
int num=0;
int bt,root;
void tarjan(int u){
dfn[u]=low[u]=++num;
q.push(u);
if(u==root&&head[u]==0){//特判不与任何点联通的情况
b[++bt].push_back(u);
return;
}
int v;
for(int i=head[u];i;i=a[i].nt){
v=a[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
bt++;
int x;
do{
x=q.top();q.pop();
b[bt].push_back(x);
}while(x!=v);
b[bt].push_back(u);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
root=i;
tarjan(i);
}
}
return 0;
}
六，\(tarjan\)应用五：求解无向图边双连通分量（\(e-DCC\)）(然后可以进行缩点)
（1）无向图边双连通分量（\(e-DCC\)）的定义：
\(~~~~~~~~\)若一个无向图不存在桥(割边)，称它为“边双连通图”，即删除任意一条边都连通。
\(~~~~~~~~\)无向图的极大边双连通子图称为“边双连通分量”。(\(e-DCC\))
（2）算法思路：
\(~~~~~~~~\)首先，求解的过程基本上同求解割边（桥）的过程差不多，还是老样子，我们用一个栈储存当前已经遍历到且没有找到所在的\(e-DCC\)的点。
\(~~~~~~~~\)我们想一想，如果有\(u-v\)的边为割边且\(u→v\)为树边，就是意味着此时\(v\)节点通过除了这条割边外的边访问不到不在它子树内的点，那么以\(v\)为根节点的子树就同属一个\(e-DCC\)，而此时\(dfn[v]=low[v]\)。
\(~~~~~~~~\)那么，就和求解\(SCC\)时一样，在\(tarjan\)的末尾加上一个判断，若符合条件就将栈中在\(v\)前面的节点和\(v\)出栈，这些节点就同属于一个\(e-DCC\)。
\(~~~~~~~~\)若要进行缩点的话，和之前一样，用数组\(color\)将出栈的元素标记就可以了。
（3）代码+注释：
#include<bits/stdc++.h>
using namespace std;
const int N=5001,M=10001;
int n,m;
struct node{
int to,nt;
}a[M*2];
int head[N],at=1;//注意，从1开始
void add(int x,int y){
a[++at].nt=head[x],head[x]=at,a[at].to=y;
}
int dfn[N],low[N];
bool vis[M*2+100],v[N];
int color[N];
int num=0;
stack<int> q;
int tot;
void tarjan(int u,int k){
dfn[u]=low[u]=++num;
q.push(u);
int v;
for(int i=head[u];i;i=a[i].nt){
v=a[i].to;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(i!=(k^1)) low[u]=min(low[u],dfn[v]);
}
//同求解割边一样
if(low[u]==dfn[u]){//判断是否符合条件
tot++;
do{
v=q.top();q.pop();
color[v]=tot;
}while(v!=u);
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(1,0);
}
return 0;
}