Tarjan算法
在介绍算法之前，首先引入时间戳和追溯点的概念。时间戳: dfn[u]表示 u结点深度优先遍历的序号。
追溯点: low[u]表示 u结点或u的子孙能通过非父子边追溯到的dfn最小的结点序号。即回到最早的过去
例如，在深度优先搜索中，每个点的时间戳和追溯点求解过程如下。
初始时，dfn[u]=low[u], 如果该结点的邻接点未被访问，则一直深度优先遍历，1- -2-3-5-6- -4， 此时4的邻接点1已被访问，且1不是4的父节点，4的父节点是6 (深度优先搜索树上的父结点)。
那么4号结点能回到最早的过去是1号结点( dfn=1 )，因此low[4]=min(low[4],dfn[1])=1。返回时，更新路径上所有祖先结点的low值，因为子孙能回到的追溯点，其祖先也能回到
如图所示。
1.无向图的桥判定法则:·
无向边(x.y)是桥，当且仅当搜索树上存在x的一个子节点y满足:
low[y] > dfm[x]
就是说，孩子的low值比自己的dfn.值大，则该结点到这个孩子的边为桥。下图中，边(5,7)，5的子节点7,满足low[7]>dfmn[5]，因此该边为桥。
实验代码
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt;
struct Edge//采用链式前向星存储
{
int to,next;
}e[maxn<<1];
int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void tarjan(int u,int fa)//u当前节点 fa:u的父节点
{
dfn[u]=low[u]=++num;//结点的dfn和low 进行初始化
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;//v:u的临界点 也是子节点
if(v==fa)//如果v是u的父节点,则直接结束. 因为判断桥时,要的是当前节点和其子节点..
continue;
if(!dfn[v])//v未访问过
{
tarjan(v,u); //进行深度优先遍历
low[u]=min(low[u],low[v]);//更新父节点的low值,孩子能到达的,父亲一定也能到达.
if(low[v]>dfn[u])//如果孩子结点的Low值 > 父节点的dfn则说明u是桥.
cout<<u<<"—"<<v<<"是桥"<<endl;
}
else//v已被访问, 且u-->v 所以 更新u的low值.
low[u]=min(low[u],dfn[v]);
}
}
void init()
{
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
cnt=num=0;
}
int main()
{
while(cin>>n>>m)
{
init();
int u,v;
while(m--)
{
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)//验证每个节点是否都已经遍历过了
if(!dfn[i])
tarjan(1,0);
}
return 0;
}
2.无向图的割点割点判定法则
若x不是根结点，则x是割点，当且仅当搜索树上存在x的一.个子节点y，满足:
low[y]≥dfm[x]
若x是根结点，则x是割点，当且仅当搜索树上存在至少两个子节点，满足上述条件。就是说，如果不是根，孩子的low值大于等于自己的dfn值，该结点就是割点;如果是根，至少需要两个孩子满足条件。
下图中，5的子节点7，满足low[7]>dfn[5]，因此5是割点。
实验代码
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt,root;
struct Edge
{
int to,next;
}e[maxn<<1];
int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++num;
int count=0;//用于计数 ,因为跟节点必须有两个节点而且子节点的low>= 根节点才说明根节点是割点.
for(int i=head[u];i;i=e[i].next)//访问当前节点u的临界点.
{
int v=e[i].to;
if(v==fa)
continue;
if(!dfn[v])
{
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
count++;
if(u!=root||count>1)//如果不是跟则,割点已找到.如果是根,则应该判断count是否>=2..
cout<<u<<"是割点"<<endl;
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
void init()
{
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
cnt=num=0;
}
int main()
{
while(cin>>n>>m)
{
init();
int u,v;
while(m--)
{
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
{
root=i;
tarjan(i,0);
}
}
return 0;
}
3.有向图的强连通分量
算法步骤:
1)深度优先遍历结点， 第一次访问结点x时，将x入栈，且dfn[x]=low[x]=++num;
2)遍历 x的所有邻接点y,
- 若y没被访问，则递归访问y,返回时更新low[x]=min(low[x]low[y]);
- 若y已被访问且在栈中，则令low[x]=min(low[x],dfn[y]);
- x 回溯之前，判断如果low[x]=dfn[x], 则从找中不断弹出结点，直到x出栈停止。
弹出的结点就是一一个连通分量。
实验代码
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt;
stack<int>s;
bool ins[maxn];
struct Edge
{
int to,next;
}e[maxn<<1];
int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void tarjan(int u)
{
low[u]=dfn[u]=++num;
ins[u]=true;
s.push(u);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
int v;
cout<<"连通分量：";
do
{
v=s.top();
s.pop();
cout<<v<<" ";
ins[v]=false;
}while(v!=u);
cout<<endl;
}
}
void init()
{
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(ins,0,sizeof(ins));
cnt=num=0;
}
int main()
{
while(cin>>n>>m)
{
init();
int u,v;
while(m--)
{
cin>>u>>v;
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
}
return 0;
}
查看3道真题和解析