Tarjan算法

在介绍算法之前,首先引入时间戳和追溯点的概念。时间戳: dfn[u]表示 u结点深度优先遍历的序号。
追溯点: low[u]表示 u结点或u的子孙能通过非父子边追溯到的dfn最小的结点序号。即回到最早的过去
例如,在深度优先搜索中,每个点的时间戳和追溯点求解过程如下。
初始时,dfn[u]=low[u], 如果该结点的邻接点未被访问,则一直深度优先遍历,1- -2-3-5-6- -4, 此时4的邻接点1已被访问,且1不是4的父节点,4的父节点是6 (深度优先搜索树上的父结点)。


那么4号结点能回到最早的过去是1号结点( dfn=1 ),因此low[4]=min(low[4],dfn[1])=1。返回时,更新路径上所有祖先结点的low值,因为子孙能回到的追溯点,其祖先也能回到
如图所示。

1.无向图的桥判定法则:·

无向边(x.y)是桥,当且仅当搜索树上存在x的一个子节点y满足:
low[y] > dfm[x]
就是说,孩子的low值比自己的dfn.值大,则该结点到这个孩子的边为桥。下图中,边(5,7),5的子节点7,满足low[7]>dfmn[5],因此该边为桥。

实验代码
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt;
struct Edge//采用链式前向星存储 
{
   
	int to,next;
}e[maxn<<1];

int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
   
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;	
}
void tarjan(int u,int fa)//u当前节点 fa:u的父节点 
{
   
	dfn[u]=low[u]=++num;//结点的dfn和low 进行初始化 
	for(int i=head[u];i;i=e[i].next)
	{
   
		int v=e[i].to;//v:u的临界点 也是子节点 
		if(v==fa)//如果v是u的父节点,则直接结束. 因为判断桥时,要的是当前节点和其子节点.. 
			continue;
		if(!dfn[v])//v未访问过 
		{
   
			tarjan(v,u); //进行深度优先遍历 
			low[u]=min(low[u],low[v]);//更新父节点的low值,孩子能到达的,父亲一定也能到达. 
			if(low[v]>dfn[u])//如果孩子结点的Low值 > 父节点的dfn则说明u是桥. 
				cout<<u<<"—"<<v<<"是桥"<<endl; 
		}
		else//v已被访问, 且u-->v 所以 更新u的low值. 
			low[u]=min(low[u],dfn[v]);
	}
}

void init()
{
   
	memset(head,0,sizeof(head));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	cnt=num=0;
}

int main()
{
   
	while(cin>>n>>m)
	{
   
		init();
		int u,v;
		while(m--)
		{
   
			cin>>u>>v;
			add(u,v);
			add(v,u);
		}
		for(int i=1;i<=n;i++)//验证每个节点是否都已经遍历过了 
			if(!dfn[i])
				tarjan(1,0);
	}
	return 0;
}

2.无向图的割点割点判定法则

若x不是根结点,则x是割点,当且仅当搜索树上存在x的一.个子节点y,满足:
low[y]≥dfm[x]
若x是根结点,则x是割点,当且仅当搜索树上存在至少两个子节点,满足上述条件。就是说,如果不是根,孩子的low值大于等于自己的dfn值,该结点就是割点;如果是根,至少需要两个孩子满足条件。

下图中,5的子节点7,满足low[7]>dfn[5],因此5是割点。


实验代码
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt,root;
struct Edge
{
   
	int to,next;
}e[maxn<<1];

int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
   
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;	
}
void tarjan(int u,int fa)
{
   
	dfn[u]=low[u]=++num;
	int count=0;//用于计数 ,因为跟节点必须有两个节点而且子节点的low>= 根节点才说明根节点是割点. 
	for(int i=head[u];i;i=e[i].next)//访问当前节点u的临界点. 
	{
   
		int v=e[i].to;
		if(v==fa) 
			continue;
		if(!dfn[v])
		{
   
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
   
				count++;
				if(u!=root||count>1)//如果不是跟则,割点已找到.如果是根,则应该判断count是否>=2.. 
					cout<<u<<"是割点"<<endl; 
			}	
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}

void init()
{
   
	memset(head,0,sizeof(head));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	cnt=num=0;
}

int main()
{
   
	while(cin>>n>>m)
	{
   
		init();
		int u,v;
		while(m--)
		{
   
			cin>>u>>v;
			add(u,v);
			add(v,u);
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i])
			{
   
				root=i;
				tarjan(i,0);
			 } 
	}
	return 0;
}

3.有向图的强连通分量

算法步骤:
1)深度优先遍历结点, 第一次访问结点x时,将x入栈,且dfn[x]=low[x]=++num;
2)遍历 x的所有邻接点y,

  • 若y没被访问,则递归访问y,返回时更新low[x]=min(low[x]low[y]);
  • 若y已被访问且在栈中,则令low[x]=min(low[x],dfn[y]);
  1. x 回溯之前,判断如果low[x]=dfn[x], 则从找中不断弹出结点,直到x出栈停止。
    弹出的结点就是一一个连通分量。

实验代码
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1000+5;
int n,m;
int head[maxn],cnt;
stack<int>s;
bool ins[maxn];
struct Edge
{
   
	int to,next;
}e[maxn<<1];

int low[maxn],dfn[maxn],num;
void add(int u,int v)
{
   
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;	
}
void tarjan(int u)
{
   
	low[u]=dfn[u]=++num;
	ins[u]=true;
	s.push(u);
	for(int i=head[u];i;i=e[i].next)
	{
   
		int v=e[i].to;
		if(!dfn[v])
		{
   
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
   
		int v;
		cout<<"连通分量:";
		do
		{
   
			v=s.top();
			s.pop();
			cout<<v<<" ";
			ins[v]=false;
		}while(v!=u);
		cout<<endl;
	}
}

void init()
{
   
	memset(head,0,sizeof(head));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(ins,0,sizeof(ins));
	cnt=num=0;
}

int main()
{
   
	while(cin>>n>>m)
	{
   
		init();
		int u,v;
		while(m--)
		{
   
			cin>>u>>v;
			add(u,v);
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i])
				tarjan(i);
	}
	return 0;
}

全部评论

相关推荐

lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务