【学习笔记】Tarjan
- 作者: 五速梦信息网
- 时间: 2026年04月04日 13:55
前言
正文凡事都得靠自己 –bobo
for(i=head[x];i!=0;i=e[i].next)
{
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
}<br/>
else<br/>
{<br/>
if(ins[e[i].to]==1)//ins[x]表示x是否在栈内<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl ‘\n’
struct node
{
int next,to;<br/>
}e[100001];
vector<int>scc[100001];
stack<int>s;
int head[100001],dfn[100001],low[100001],ins[100001],vis[100001],c[100001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x)
{
int i,k=0;<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
ins[x]=1;<br/>
s.push(x);<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
}<br/>
else<br/>
{<br/>
if(ins[e[i].to]==1)//说明e[i].to是祖先节点or左子树节点<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}<br/>
if(dfn[x]==low[x])//如果这里构成了一个强连通分量<br/>
{<br/>
ans++;//ans是强连通分量的编号<br/>
while(x!=k)//将这个强连通分量内的点标记一下<br/>
{<br/>
k=s.top();<br/>
ins[k]=0;<br/>
c[k]=ans;//c[k]表示k属于哪个强连通分量内<br/>
scc[ans].push_back(k);<br/>
s.pop();<br/>
}<br/>
}<br/>
}
int main()
{
int n,m,i,j,u,v;<br/>
cin>>n>>m;<br/>
for(i=1;i<=m;i++)<br/>
{<br/>
cin>>u>>v;<br/>
add(u,v);<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)<br/>
{<br/>
tarjan(i);<br/>
}<br/>
}<br/>
cout<<ans<<endl;<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(vis[c[i]]==0)<br/>
{<br/>
vis[c[i]]=1;<br/>
sort(scc[c[i]].begin(),scc[c[i]].end());<br/>
for(j=0;j<scc[c[i]].size();j++)<br/>
{<br/>
cout<<scc[c[i]][j]<<" ";<br/>
}<br/>
cout<<endl;<br/>
}<br/>
}<br/>
return 0;<br/>
}
scc=0;
while(x!=k)
{
k=s.top();<br/>
ins[k]=0;<br/>
scc++;<br/>
s.pop();<br/>
}
if(scc!=1)
{
maxin=min(maxin,scc);<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl ‘\n’
struct node
{
int next,to;<br/>
}e[100001];
stack<int>s;
int head[100001],dfn[100001],low[100001],ins[100001],scc[100001],c[100001],u[100001],v[100001],anss[100001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x)
{
int i,k=0;<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
ins[x]=1;<br/>
s.push(x);<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
}<br/>
else<br/>
{<br/>
if(ins[e[i].to]==1)<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}<br/>
if(dfn[x]==low[x])<br/>
{<br/>
ans++;<br/>
while(x!=k)<br/>
{<br/>
k=s.top();<br/>
ins[k]=0;<br/>
c[k]=ans;<br/>
scc[ans]++;<br/>
s.pop();<br/>
}<br/>
}<br/>
}
void search(int rt,int x,int sum)
{
if(anss[x]==0)<br/>
{<br/>
search(rt,v[x],sum+1);<br/>
}<br/>
else<br/>
{<br/>
anss[rt]=anss[x]+sum;<br/>
return;<br/>
}<br/>
}
int main()
{
int n,i,j,sum;<br/>
cin>>n;<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
u[i]=i;<br/>
cin>>v[i];<br/>
add(u[i],v[i]);<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)<br/>
{<br/>
tarjan(i);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(u[i]==v[i])//给自环打个标记<br/>
{<br/>
anss[i]=1;<br/>
}<br/>
else<br/>
{<br/>
if(scc[c[u[i]]]>=2)<br/>
{<br/>
anss[i]=scc[c[u[i]]];<br/>
}<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(anss[i]==0)<br/>
{<br/>
search(u[i],v[i],1);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
cout<<anss[i]<<endl;<br/>
}<br/>
return 0;<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl ‘\n’
struct node
{
int next,to;<br/>
}e[400001];
int head[400001],dfn[400001],low[400001],flag[400001],cnt=0,tot=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x,int fa)
{
int i,k=0,son=0;//son用于存子节点个数<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to,fa);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
if(low[e[i].to]>=dfn[x])<br/>
{<br/>
son++;<br/>
if(x!=fa||son>=2)<br/>
{<br/>
flag[x]=1;<br/>
}<br/>
}<br/>
}<br/>
else<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}
int main()
{
int n,m,i,u,v,sum=0;<br/>
cin>>n>>m;<br/>
for(i=1;i<=m;i++)<br/>
{<br/>
cin>>u>>v;<br/>
add(u,v);<br/>
add(v,u);<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)<br/>
{<br/>
tarjan(i,i);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
sum+=flag[i];<br/>
}<br/>
cout<<sum<<endl;<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(flag[i]==1)<br/>
{<br/>
cout<<i<<" ";<br/>
}<br/>
}<br/>
return 0;<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl ‘\n’
struct node
{
int next,to;<br/>
}e[4000001];
vector<int>v_dcc[4000001];
stack<int>s;
int head[4000001],dfn[4000001],low[4000001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x,int fa)
{
int i,k=0;<br/>
if(x==fa&&head[x]==0)//孤立点判定<br/>
{<br/>
ans++;<br/>
v_dcc[ans].push_back(x);<br/>
}<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
s.push(x);<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to,fa);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
if(low[e[i].to]>=dfn[x])<br/>
{<br/>
ans++;<br/>
v_dcc[ans].push_back(x);<br/>
while(e[i].to!=k)//弹栈时不能弹出割点，因为割点属于多个点双连通分量<br/>
{<br/>
k=s.top();<br/>
v_dcc[ans].push_back(k);<br/>
s.pop();<br/>
}<br/>
}<br/>
}<br/>
else<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}
int main()
{
int n,m,i,j,u,v;<br/>
cin>>n>>m;<br/>
for(i=1;i<=m;i++)<br/>
{<br/>
cin>>u>>v;<br/>
if(u!=v)//重边会影响结果，记得特判<br/>
{<br/>
add(u,v);<br/>
add(v,u);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)//注意图可能不连通<br/>
{<br/>
tarjan(i,i);<br/>
}<br/>
}<br/>
cout<<ans<<endl;<br/>
for(i=1;i<=ans;i++)<br/>
{<br/>
cout<<v_dcc[i].size()<<" ";<br/>
for(j=0;j<v_dcc[i].size();j++)<br/>
{<br/>
cout<<v_dcc[i][j]<<" ";<br/>
}<br/>
cout<<endl;<br/>
}<br/>
return 0;<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl ‘\n’
struct node
{
int next,to;<br/>
}e[4000001];
vector<int>v_dcc[4000001];
stack<int>s;
int head[4000001],dfn[4000001],low[4000001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x,int fa)
{
int i,k=0;<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
s.push(x);<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to,fa);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
if(low[e[i].to]>=dfn[x])<br/>
{<br/>
ans++;<br/>
v_dcc[ans].push_back(x);<br/>
while(e[i].to!=k)<br/>
{<br/>
k=s.top();<br/>
v_dcc[ans].push_back(k);<br/>
s.pop();<br/>
}<br/>
}<br/>
}<br/>
else<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}
bool cmp(vector<int> x,vector<int> y)
{
for(int i=0;i<min(x.size(),y.size());i++)<br/>
{<br/>
if(x[i]!=y[i])<br/>
{<br/>
return x[i]<y[i];<br/>
}<br/>
}<br/>
return x.size()<y.size();<br/>
}
int main()
{
int n,m,i,j,u,v;<br/>
cin>>n>>m;<br/>
for(i=1;i<=m;i++)<br/>
{<br/>
cin>>u>>v;<br/>
if(u!=v)<br/>
{<br/>
add(u,v);<br/>
add(v,u);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)<br/>
{<br/>
tarjan(i,i);<br/>
}<br/>
}<br/>
cout<<ans<<endl;<br/>
for(i=1;i<=ans;i++)<br/>
{<br/>
sort(v_dcc[i].begin(),v_dcc[i].end());<br/>
}<br/>
sort(v_dcc+1,v_dcc+1+ans,cmp);<br/>
for(i=1;i<=ans;i++)<br/>
{<br/>
for(j=0;j<v_dcc[i].size();j++)<br/>
{<br/>
cout<<v_dcc[i][j]<<" ";<br/>
}<br/>
cout<<endl;<br/>
}<br/>
return 0;<br/>
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl ‘\n’
struct node
{
int next,to,flag;<br/>
}e[4000001];
vector<int>e_dcc[4000001];
stack<int>s;
int head[4000001],dfn[4000001],low[4000001],flag[4000001],dout[4000001],cnt=1,tot=0,ans=0;
void add(int u,int v)
{
cnt++;<br/>
e[cnt].next=head[u];<br/>
e[cnt].flag=0;<br/>
e[cnt].to=v;<br/>
head[u]=cnt;<br/>
}
void tarjan(int x,int fa)
{
int i,k=0;<br/>
tot++;<br/>
dfn[x]=low[x]=tot;<br/>
s.push(x);<br/>
for(i=head[x];i!=0;i=e[i].next)<br/>
{<br/>
if(dfn[e[i].to]==0)<br/>
{<br/>
tarjan(e[i].to,i);<br/>
low[x]=min(low[x],low[e[i].to]);<br/>
if(low[e[i].to]>dfn[x])//割边判定法则<br/>
{<br/>
e[i].flag=e[i^1].flag=1;<br/>
}<br/>
}<br/>
else<br/>
{<br/>
if((fa^1)!=i)<br/>
{<br/>
low[x]=min(low[x],dfn[e[i].to]);<br/>
}<br/>
}<br/>
}<br/>
if(low[x]==dfn[x])//这里可以用DFS替代<br/>
{<br/>
ans++;<br/>
while(x!=k)<br/>
{<br/>
k=s.top();<br/>
s.pop();<br/>
e_dcc[ans].push_back(k);<br/>
}<br/>
}<br/>
}
int main()
{
int n,m,i,j,u,v;<br/>
cin>>n>>m;<br/>
for(i=1;i<=m;i++)<br/>
{<br/>
cin>>u>>v;<br/>
if(u!=v)<br/>
{<br/>
add(u,v);<br/>
add(v,u);<br/>
}<br/>
}<br/>
for(i=1;i<=n;i++)<br/>
{<br/>
if(dfn[i]==0)<br/>
{<br/>
tarjan(i,0);<br/>
}<br/>
}<br/>
cout<<ans<<endl;<br/>
for(i=1;i<=ans;i++)<br/>
{<br/>
cout<<e_dcc[i].size()<<" ";<br/>
for(j=0;j<e_dcc[i].size();j++)<br/>
{<br/>
cout<<e_dcc[i][j]<<" ";<br/>
}<br/>
cout<<endl;<br/>
}<br/>
return 0;<br/>
}
学校的课件（不方便放出）
《算法竞赛进阶指南》———李煜东
强连通分量 | 割点和桥 |双连通分量
- 上一篇： 【学习总结】GirlsInAI ML
- 下一篇： 【虚拟化实战】容灾设计之四VPLEX
相关文章
-
【学习总结】GirlsInAI ML
【学习总结】GirlsInAI ML
- 互联网
- 2026年04月04日
-
【学习总结】Info.plist和pch文件的作用
【学习总结】Info.plist和pch文件的作用
- 互联网
- 2026年04月04日
-
【原】AFNetworking源码阅读（二）
【原】AFNetworking源码阅读（二）
- 互联网
- 2026年04月04日
-
【虚拟化实战】容灾设计之四VPLEX
【虚拟化实战】容灾设计之四VPLEX
- 互联网
- 2026年04月04日
-
【虚拟化实战】容灾设计之三Stretched Cluster
【虚拟化实战】容灾设计之三Stretched Cluster
- 互联网
- 2026年04月04日
-
【新手友好】用Pyspark和GraphX解析复杂网络数据
【新手友好】用Pyspark和GraphX解析复杂网络数据
- 互联网
- 2026年04月04日
