大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
Tarjan
0.2
目录
基本概念
Tarjan是一种求有向图强联通分量的算法, 是用dfs实现以及时间戳标记访问最短时间的.Tarjan算法中每个点都需要扩展边,为了存储方便,推荐使用邻接表.Tarjan算法的优势在于其灵活性,基础代码可以直接适用于多数情况.常见于dfs序.
运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进结合.出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。
基础代码
#include <cstdio>
#include <stack>
#include <iostream>
using namespace std;
int f[11],ro,dfn[11],low[11],g[11],c;
bool v[11];
stack<int> q;
struct $
{
int s,t,ne;
}a[11];
void Tarjan(int co)
{
/*dfn层数 low最早到达时间*/
dfn[co]=low[co]=++c;//标记当前时间戳
q.push(co);//将点压入栈
for(int k=f[co];k;k=a[k].ne)
{
int i=a[k].t;
if(v[i]) continue;//如果已经访问过,就跳过
//dfs
if(!dfn[i])//这个表示该点是否已经被打上时间戳
{
Tarjan(i);
low[co]=min(low[co],low[i]);
//如果否,打上最小时间戳.
}
else
low[co]=min(low[co],dfn[i]);
}
if(dfn[co]==low[co])//找到根
{
sum++;//记录分量数量
int i;
while(i!=co)
{
i=q.top();
v[i]=true;//标记找到
g[i]=co;//记录每个点的根,在缩图时用
q.pop();
}
v[co]=1;
if(!q.empty())q.pop();//有些特殊情况不判断可能会崩溃
}
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)//链式前向星
while(1)
{
scanf("%d",&v);
if(!v) break;
a[++ro].s=i;
a[ro].t=v;
a[ro].ne=f[i];
f[i]=v;
}
for(int i=1;i<=n;i++)//扩展
if(!dfn[i])
{
c=0;
Tarjan(i);
}
return 0;
}
常见变换
(main())
if(c==1)//c标记强联通分量数量
printf("该图强联通\n");
void rebuild()//缩图去环
{
for(int i=1;i<=ro/*路的数量*/;i++)
if(g[a[i].s]!=g[a[i].t])//如果路的两端分别在两个强联通分量中
合并;
}
void degree()//入度出度计算,紧接rebuild()
{
int ina=0,outa=0,vi[11]={
0},vo[11]={
0};//标记点是否有出入度,可根据需要改为计数
for(int i=1;i<=ro)
if(g[a[i].s]!=g[a[i].t])
{
//在这里改为++即可
vi[a[i].t]=1;
vo[a[i].s]=1;
}
for(int i=1;i<=n;i++)
{
if(!vi[i]) ina++;
if(!vo[i]) outa++;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215456.html原文链接：https://javaforall.net
