在有向图中,如果2个顶点之间存在至少一条路径,则称这2个顶点强连通。如果有向图G中任意2个顶点都强连通,则称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量。
强连通分量的求法分为主流的2种,一种是Kosaraju,做2次DFS。另外一种就是伟大的计算机科学家Tarjan发明的算法,该算法只需要做一次DFS即可,比Kosaraju更快。
网上关于Tarjan算法的介绍很多,我推荐Byvoid大牛写的:
有向图强连通分量的Tarjan算法
这篇文章被wiki推荐,非常经典,看完秒懂
下面我们先来做一道模板题:
HDU1269 --- 迷宫城堡
分析:Tarjan模板题,看整张图是不是一张强连通图
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
struct Edge{
int to,next;
}edge[maxn];
int n,m,tot,head[maxn];
int low[maxn],dfn[maxn],num[maxn],s[maxn],belong[maxn];
bool Instack[maxn];
int Index,scc,top;
void init(){
tot=0;
memset(head,-1,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(num,0,sizeof(num));
memset(s,0,sizeof(s));
memset(belong,0,sizeof(belong));
memset(Instack,false,sizeof(Instack));
Index=scc=top=0;
}
void add(int u,int v){
edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void Tarjan(int u){
int v;
dfn[u]=low[u]=++Index;
s[top++]=u;
Instack[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next){
v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(Instack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc++;
do{
v=s[--top];
Instack[v]=false;
belong[v]=scc;
num[scc]++;
}while(u!=v);
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0) break;
init();
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) Tarjan(i);
}
if(scc==1) printf("Yes\n");
else printf("No\n");
}
return 0;
}
其实缩点也是运用Tarjan求强连通分量的方法,不过对于一些贡献具有传导性的问题有时候需要缩点,比如友情传递、路上权值等。
缩点的思想也很显然,因为强连通分量中的每两个点都是强连通的,故可以将一个强连通分量当做一个超级点,而点权按题意来定。
如下图所示就是一个缩点的例子
同样关于缩点问题,我们来看一道简单的模板题
BZOJ1051 --- [HAOI2006]受欢迎的牛
分析:首先对于一个强连通分量里面的所有点都满足条件,于是我们对图进行缩点,这样我们得到的所有点都不是强连通的,现在整张图就是一个DAG。我们考虑出度为0的点,则在图中至少存在一个出度为0的点,如果超过1个,则必不可能满足条件,否则这个点就满足条件。这个点很可能为所有强连通分量构成的超级点,所以也就是要求的也就是这个强连通分量中点的个数
#include "bits/stdc++.h"
using namespace std;
const int maxn=5e4+10;
vector<int>g[maxn];
int n,m;
int low[maxn],dfn[maxn],s[maxn],num[maxn],belong[maxn];
bool Instack[maxn];
int Index,scc,top;
void Tarjan(int u){
int v;
low[u]=dfn[u]=++Index;
s[top++]=u;
Instack[u]=true;
for(int i=0;i<g[u].size();i++){
v=g[u][i];
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(Instack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
++scc;
do{
v=s[--top];
Instack[v]=false;
belong[v]=scc;
num[scc]++;
}while(u!=v);
}
}
int cnt[maxn],du[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) Tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
if(belong[i]!=belong[v]){
du[belong[i]]++;
}
}
cnt[belong[i]]++;
}
int tmp=0,ans=0;
for(int i=1;i<=scc;i++){
if(du[i]==0){
tmp++;
ans=cnt[i];
}
}
if(tmp>1) printf("0\n");
else printf("%d\n",ans);
return 0;
}
原文:https://www.cnblogs.com/gzgywh/p/10713358.html