【小白入门向】tarjan算法+codevs1332上白泽慧音…

2018-06-17 23:47:59来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

一、【前言】关于tarjan

tarjan算法是由Robert Tarjan提出的求解有向图强连通分量的算法。

那么问题来了找蓝翔!(划掉)什么是强连通分量?

我们定义:如果两个顶点互相连通(即存在A到B和B到A的通路),则称这两个点强连通。对于一个有向图G,若是G中任意两点都强连通,则称G是一个强连通图。有向图的极大强连通子图,称为该图的强连通分量

对于下图,{1,2,3,4}、{5}、{6}分别是它的强连通分量。

那么tarjan是如何找到这些强连通分量的呢?

说白了tarjan就是dfs,每个强连通分量都是搜索树中的一颗子树。搜索时,我们把当前搜索树中未处理过的点加入一个堆栈,回溯时从栈顶依次取出元素判断他们是否属于一个强连通分量。

我们对dfs的过程中添加如下定义:
1、dfn[i]:代表搜索点i的次序编号;

2、low[i]:代表点i所能回溯到的栈中最早的次序编号。

当dfn[i]=low[i]时,以i为根的子树上的所有点便构成一个强连通分量。

 

二、tarjan算法c语言实现

那么要如何使用程序来实现tarjan算法呢?

大致思路如下:
1、从一个未被处理过的点i开始,给它结合一个次序编号并把它压入栈中,然后标记点表示其已入栈,令low[i]=dfn[i]=次序编号;

2、遍历每条以i为起点的边,若边的终点j未被处理过,就对其进行操作1~3,令low[i]=min(low[i],low[j]);

3、找到的点j若是被处理过,则判断其是否在栈中:若在,则令low[i]=min(low[i],dfn[j]);

4、若是dfn[i]=low[i],就将栈顶到i间的所有元素弹出,它们便是一个强连通分量;

5、重复1~4,直至不存在点未被处理。

贴上伪代码(转自百度百科词条——tarjan算法)

 1 tarjan(u)
 2 {
 3     DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值
 4     Stack.push(u)//将节点u压入栈中
 5     for each(u,v) in E//枚举每一条边
 6         if (visnotvisted)//如果节点v未被访问过
 7             tarjan(v)//继续向下找
 8             Low[u]=min(Low[u],Low[v])
 9         else if (vinS)//如果节点v还在栈内
10                 Low[u]=min(Low[u],DFN[v])
11     if (DFN[u]==Low[u])//如果节点u是强连通分量的根
12     repeat{
13         v=S.pop//将v退栈,为该强连通分量中一个顶点
14         printv
15         until(u==v)
16     }
tarjan伪代码

三、codevs1332题解

http://codevs.cn/problem/1332/←_←挂上原题链接

这是一道全♂裸的tarjan题,我们只需跑一遍tarjan,并对所有强连通分量染色,最后输出最大的就好

代码如下:

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 struct node
 5 {
 6     int v;
 7     int next;
 8 }e[50010];//邻接表记录有向图 
 9 int stack[5010],top;//
10 int dfn[5010],low[5010],index;//index用于记录次序编号 
11 bool vis[5010];//判断点是否在栈内 
12 int st[5010],cnt; 
13 int color[5010],s[5010],num;//用于染色并记录颜色种类 
14 void build(int a,int b)
15 {
16     e[++cnt].v=b;
17     e[cnt].next=st[a];
18     st[a]=cnt;
19 }//建图,没什么好说的 
20 void tarjan(int x)
21 {
22     dfn[x]=++index;
23     low[x]=index;
24     vis[x]=true;
25     stack[++top]=x;//当前点入栈 
26     int i;
27     for(i=st[x];i!=0;i=e[i].next)//枚举以当前点为起点的边 
28     {
29         int temp=e[i].v;//temp为当前被枚举边的终点 
30         if(!dfn[temp])//如果当前边终点未被处理 
31         {
32             tarjan(temp);
33             low[x]=min(low[x],low[temp]);
34         }
35         else if(vis[temp])low[x]=min(low[x],dfn[temp]);
36     }
37     if(dfn[x]==low[x])
38     {
39         vis[x]=false;
40         color[x]=++num;//给当前强连通分量染上新颜色 
41         s[num]++;//给当前强连通分量里的点染色 
42         while(stack[top]!=x)//栈顶元素依次出栈 
43         {
44             s[num]++;
45             color[stack[top]]=num;
46             vis[stack[top--]]=false;
47         }
48         top--;
49     }
50 }
51 int main()
52 {
53     int n,m,i,a,b,t,ans=0,f;
54     scanf("%d%d",&n,&m);
55     for(i=1;i<=m;i++)
56     {
57         scanf("%d%d%d",&a,&b,&t);
58         build(a,b);
59         if(t-1)build(b,a);
60     }
61     for(i=1;i<=n;i++)
62     {
63         if(!dfn[i])tarjan(i);
64     }
65     for(i=1;i<=n;i++)
66     {
67         if(s[color[i]]>ans)//找到被染色最多的强连通分量(因为要求字典序,所以使用'>') 
68         {
69             ans=s[color[i]];
70             f=i;
71         }
72     }
73     printf("%d\n",ans);
74     for(i=1;i<=n;i++)
75     {
76         if(color[i]==color[f])printf("%d ",i);//输出被染成最大强连通分量的颜色的点 
77     }
78     return 0;
79 }
codevs1332

弱弱地说一句,本蒟蒻码字也不容易,转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/5866191.html

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2016 大连网赛---Function(单调栈)

下一篇:杨氏矩阵定义及其查找的实现C++