Tarjan 算法是基于对图 dfs 的算法。时间复杂度一般为 ，因为边和点一般最多访问一次。
退役的那场 NOIP，第三题需要边双连通分量缩点转化，不会写，警钟敲烂。希望后辈们基础要扎实。
转化完之后是简单 DP。其实第三题就没好好想，考试完交流才发现第三题第二简单。
强连通分量
这个名字听起来很高大上。
注意，强连通分量是有向图中的定义。
定义
两个顶点强连通的定义：
两点 、 之间存在着 到 的路径及 到 的路径。
强连通图的定义：
如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。
强连通分量的定义：
有向图的极大强连通子图，称为强连通分量（单个点也可是强连通分量）。
意思就是说，这个子图应是最大的。
以下图举例：
[1]<--[2]-->[3]
| ^ ^
v | |
[4]-->[5]-->[6]
顶点 1，2 是强连通的；分别由 1245，3，6 构成的子图都是这个图的强连通分量。
求强连通分量
Tarjan 算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一颗子树。
搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以盘对栈顶到栈中的节点是否为一个强连通分量。
定义 为节点 u 搜索的次序编号（时间戳）。 为节点 u 向子树方向能够追溯到的最早的时间戳。
由定义可以得出：
。其中，u 应为 v 的在 dfs 树上的父节点。
当 时，以 u 为根的搜索子树上所有节点是一个强连通分量。
CODE 实现
需以下变量：
dfn[N]//时间戳。
low[N]//一个节点向子树方向能够追溯到的最早的时间戳。
ins[N]//是否在栈中
stk[N]//手工栈。注意，这个栈与系统栈不同。
bel[N]//一个节点从属于哪个强连通分量。
top=0//栈的顶部指针。
scc=0//强连通分量个数。
index=0//用来戳时间戳。
主体 CODE：
void tarjan(int now)
{
dfn[now]=low[now]=(++index);//戳时间戳
ins[now]=1;stk[++top]=now;//打上入栈标记，入栈
for(int i=head[now];i;i=e[i].nxt)//枚举算符
{
int to=one.e[i].end;
if(!dfn[to])
tarjan(to),low[now]=min(low[now],low[to]);
//进行dfs，并根据前文求low_u。
else if(ins[to])
low[now]=min(low[now],dfn[to]);
//已经在栈中且访问过了，回溯，并根据前文求low_u。
else{/*无实际用处*/}
}
if(dfn[now]==low[now])//强连通分量增加了
{
scc++;
do{
int tmp=stk[top];
ins[tmp]=0;bel[tmp]=scc;
}while(now!=stk[top--]);//弹栈
}
}
//注意，一遍tarjan不一定遍历所有点，所以要tarjan所有未访问的点。
//用dfn[]判断是否访问。
例题：P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G。
割点
定义
删掉一个节点及其相邻的边，使连通块个数加一。这个节点就是割点。
tarjan 也可以求割点。原理是看一个节点的后继是否“返祖”（通过另一条路径访问到这个节点的祖先）。如下图：
[1]<--[2]-->[3]
| ^ ^
v | |
[4]-->[5]-->[6]
节点 5 就是一个割点。因为她的后继 6 不能通过“返祖”与 5 联系。
那这个呢：
[1]---[2]---[3]
| | |
| | |
[4]---[5]---[6]
//无向图
很明显没有。
求割点
首先选定一个根节点，从该根节点开始遍历整个图。
对于根节点，判断是不是割点很简单——计算其子树数量，如果有 棵及以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。
对于非根节点，若对于边 ，如果 ，说明 最早也是在 节点及之后了，此时 就是割点。
显然，如果节点 的所有孩子节点可以不通过父节点 而访问到 的祖先节点，那么说明此时去掉节点 不影响图的连通性， 就不是割点。
相反，如果节点 至少存在一个孩子顶点，必须通过父节点 才能访问到 的祖先节点，那么去掉节点 后，顶点 的祖先节点和孩子节点就不连通了，说明 是一个割点。
CODE实现
需以下变量：
cut[]//割点标记数组
dad//选定的根节点
dfn[]//时间戳。
low[]//一个节点向子树方向能够追溯到的最早的时间戳。
index=0//用来戳时间戳。
child=0//根节点子树数量
主体 CODE：
void tarjan(int now)
{
int child=0;
dfn[now]=low[now]=(++index);
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].end;
if(!dfn[to])
{
tarjan(to);
low[now]=min(low[now],low[to]);
if(low[to]>=dfn[now]&&now!=dad)
cut[now]=1;
if(now==dad) child++;
}
else low[now]=min(low[now],dfn[to]);
}
if(child>=2&&now==dad)
cut[now]=1;
}
割边（桥）
定义
删掉一条边，使连通块个数加一。这个边就是割边（桥）。
割点与桥（割边）的关系：
有割点不一定有桥,有桥一定存在割点
桥一定是割点依附的边。
求割边
与求割点类似。$low_v > dfn_u $ 就说明 是桥。
CODE 实现
与求割点类似：
void tarjan(int now,int dad)//规避儿子访问父亲的情况出现。
{
dfn[now]=low[now]=(++index);
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].end;
if(!dfn[to])
{
tarjan(to,now);
low[now]=min(low[now],low[to]);
if(low[to]>dfn[now]) cut[now]=1;
}
else if(to!=dad) low[now]=min(low[now],dfn[to]);
}
}
//割点无需规避儿子访问父亲的情况出现，原因：不影响判断。
缩点
指将强连通分量看作一个点。
CODE 实现
void build()
{
for(int now=1;now<=n;now++)
{
for(int j=big.head[now];j;j=big.e[j].nxt)
{
int to=big.e[j].end;
if(bel[now]==bel[to])
continue;
small.add(bel[now],bel[to]);
}
}
}
//big指原图，small指新图
例题
P1262 间谍网络
- 如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。
- 有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。
- 一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
- 我们已知所有受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。
总共有 个间谍（ 不超过 ）。判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
缩点+拓扑排序。参考代码：
点击查看
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
typedef long long ll;
const ll N=3000+10,inf=2147483647;
struct graph
{
struct edge{ll nxt,to;}e[N*2];
ll head[N],cnt,w[N],num[N],in[N];
graph()
{
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
memset(in,0,sizeof(in));
for(ll i=1;i<=N-1;i++) w[i]=num[i]=inf;
cnt=0;
}
void add(ll a,ll b)
{
e[++cnt]=(edge){head[a],b};
head[a]=cnt;in[b]++;
}
}one,two;
ll n,p,r,ans=0,fail=inf;
ll ins[N],stk[N],dfn[N],low[N],bel[N],scc=0,index=0,top=0;
queue<ll>q;
void tarjan(ll now)
{
dfn[now]=low[now]=++index;
stk[++top]=now;ins[now]=1;
for(ll i=one.head[now];i;i=one.e[i].nxt)
{
ll to=one.e[i].to;
if(!dfn[to])
{
tarjan(to);
low[now]=min(low[now],low[to]);
}
else if(ins[to])
{
low[now]=min(low[now],dfn[to]);
}
}
if(dfn[now]==low[now])
{
scc++;
do{
ll cur=stk[top];
bel[cur]=scc;
if(two.w[scc]>=one.w[cur])
{
two.w[scc]=one.w[cur];
two.num[scc]=min(two.num[scc],one.num[cur]);
}
ins[cur]=0;
}while(stk[top--]!=now);
}
}
void build(ll now)
{
for(ll i=one.head[now];i;i=one.e[i].nxt)
{
ll to=one.e[i].to;
if(bel[now]!=bel[to])
two.add(bel[now],bel[to]);
}
}
void fake_topo()
{
for(ll i=1;i<=scc;i++)
{
if(two.in[i]==0)
q.push(i);
}
while(!q.empty())
{
ll now=q.front();
q.pop();
if(two.w[now]==inf)
fail=min(fail,two.num[now]);
ans+=two.w[now];
}
}
void yzmain()
{
ll t1,t2;
scanf("%lld%lld",&n,&p);
for(ll i=1;i<=p;i++)
{
scanf("%lld%lld",&t1,&t2);
one.w[t1]=t2;
}
scanf("%lld",&r);
for(ll i=1;i<=r;i++)
{
scanf("%lld%lld",&t1,&t2);
one.add(t1,t2);
}
for(ll i=1;i<=n;i++)
one.num[i]=i;
for(ll i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(ll i=1;i<=n;i++)
build(i);
fake_topo();
if(fail!=inf)
{
printf("NO\n%lld\n",fail);
return;
}
printf("YES\n%lld\n",ans);
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/c9317a28769e/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
