tarjan有向图求强联通分量时间复杂度(N+M)
-
强联通：用向图中a有一条路可以到b，b有一条路可以到a；则a，b为强联通
-
强连通图：在一个有向图中，认意两点可以相通，就是强连通图
-
强联通分量：非强联通图中，强连通部分（注意一个节点到本身也是一个强联通分量）
-
树边：访问节点构建搜索树时建的边
-
返祖边：生儿子时突然生出个祖先的边
-
横叉边：右儿子想成为左儿子父亲的边（没用）
-
前向边：祖先想跨级降辈（没用）
正式进入tarjan
-
时间戳：dfs搜索时时间顺序（有小到大）dfn[]
-
追溯值：当前节点作为根节点搜索到的时间戳最小的值
low[] -
只需要树枝边和返祖边的low[]
x->y
树枝边（未访问）low[x]=min (low[x],low[y]);
返祖边（访问过）low[x]=min (low[x],dfn[y]);不能时low[y]因为还没访问
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans,tot,cnt;
//instk是判断节点是否在栈内，scc是强联通分量个数
//siz是求强联通分量的大小
vector<int> e[300000];
stack<int> zhan;
int dfn[300000],low[300000],instk[300000],scc[300000],siz[300000];
void tj(int x)
{
dfn[x]=low[x]=++tot;
zhan.push(x),instk[x]=1;
for(int y:e[x])//从数组首搜到尾
if(!dfn[y])tj(y),low[x]=min(low[x],low[y]);//树边
else if(instk[y])low[x]=min(low[x],dfn[y]);//返祖边
if(dfn[x]==low[x])
{
int y;++cnt;
while(y!=x)
{
y=zhan.top();
zhan.pop();
instk[y]=0;
scc[y]=cnt;
++siz[cnt];
}
}
}
int main()
{
cin>>n>>m;
for(;m;--m)cin>>a>>b,e[a].push_back(b);
for(int i=1;i<=n;++i)
if(dfn[i]==0)//判断是否在栈内
tj(i);
for(int i=1;i<=cnt;++i)if(siz[i]>1)++ans;
cout<<ans<<'\n';
}
缩点
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans,tot,cnt;
vector<int> e[300000];
stack<int> zhan;
int dfn[300000],chu[30000],low[300000],instk[300000],scc[300000],siz[300000];
void tj(int x)
{
dfn[x]=low[x]=++tot;
zhan.push(x),instk[x]=1;
for(int y:e[x])
if(!dfn[y])tj(y),low[x]=min(low[x],low[y]);
else if(instk[y])low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])
{
int y;++cnt;
while(y!=x)
{
y=zhan.top();
zhan.pop();
instk[y]=0;
scc[y]=cnt;
++siz[cnt];
}
}
}
int main()
{
cin>>n>>m;
for(;m;--m)cin>>a>>b,e[a].push_back(b);
for(int i=1;i<=n;++i)if(!dfn[i])tj(i);
for(int i=1;i<=n;++i)
for(int y :e[i])
if(scc[i]!=scc[y])++chu[scc[i]];
int zeros=0;
for(int i=1;i<=cnt;++i)
if(chu[i]==0) ans=siz[i],++zeros;
if(zeros>1) ans=0;
cout<<ans<<'\n';
}
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
vector<int> g[10010];
int color[10010],dfn[20020],low[20020],stack[20020],vis[10010],cnt[10010];
int deep,top,n,m,sum,ans;
void tarjan(int u)
{
dfn[u]=++deep;
low[u]=deep;
vis[u]=1;
stack[++top]=u;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(vis[v])
{
low[u]=min(low[u],low[v]);
}
}
}
if(dfn[u]==low[u])
{
color[u]=++sum;
vis[u]=0;
while(stack[top]!=u)
{
color[stack[top]]=sum;
vis[stack[top--]]=0;
}
top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
for(int i=1;i<=n;i++)
{
cnt[color[i]]++;
}
for(int i=1;i<=sum;i++)
{
if(cnt[i]>1)
{
ans++;
}
}
printf("%d\n",ans);
}