其实tarjan算法提出的思想就是DFS深度优先遍历，在遍历的过程中记录某些变量的值，来解决相关问题，下面两个经典的问题都能通过tarjan的思想去解决。在此表达对Robert Tarjan的崇高敬意。

连通

基础思想

就是通过DFS，在深度优先遍历的过程中，记录每个节点上对应的值，在编程中我们需要记录的每个节点的值有DFN(访问的次序)，inStack(是否在栈中，引入的栈是做什么的，下面会演示)，LOW(记录该节点可以追溯到的节点的时间戳)，然后通过比较DFN和LOW的值去判断该节点是否能构成连通分量。

伪代码

void varjan(节点 t)//深搜 对于与节点t相连的每个节点i 如果i没有访问过，则 varjan（i）//继续深搜 LOW[t]=min(LOW[i],LOW[t]);//回朔到该点时； 如果i访问过，并且i在栈中，那么 LOW[t]=min(LOW[t],DFN[i]); if LOW[t]==DFN[t] 输出栈中位于t前面的所有的节点为一个连通风量。

下面我们通过题目去讲解tarjan的思想，看一下是如何判断一个图是否是连通图的。 这是一个老图，了解强连通的应该可以看出来，该图有三个连通分量分别为{1，2，3，4}，{5}，{6}

那么如何利用程序去寻找该图中有那些连通分量呢？

1.我们以节点1为开始节点，去深度优先别的遍历每一个节点。

2.到节点6的时候，我们发现6没有子节点，于是判断其DFN与LOW是否相等，相等则弹出栈中6以上的所有节点为一个连通分量，可知只有6一个。

3.回溯到5，发现与节点6一样，找不到未访问的子节点。于是栈中弹出5然后继续回溯。

4.然后继续从节点2开始深度优先访问4，则4的DFN和LOW即为5；当访问4->1路线时，发现1节点已经访问过了，而且存在栈中，所以使得LOW[4]=min{DFN1,LOW[4]}=1;

5.节点4的子节点都访问完了，判断DFN[4]不等于LOW[4]，所以继续回朔到2，LOW[2]=min{LOW[4],LOW[2]}=1。又因为节点2的所有子节点也访问完了，所以判断DFN[2]不等于LOW[2]，继续回朔，访问节点3。过程是一样的，就不分析了。下面结合代码去更好的理解。

代码实现

//============================================================================ // Name : Tarjan.cpp // Author : SELOUS // Version : // Copyright : Your copyright notice // Description : Tarjan;Strongly Connected Graph //============================================================================ #include <iostream> using namespace std; #include <vector> #include <stack> #define MAXN 20//最大节点数为20 vector <int> graph[MAXN];//使用vector储存图的信息 stack <int> s;//用来储存节点信息 int belong[MAXN];//记录节点属于哪一个连通分量 int typeNum=0;//连通分量编号 //比如节点1属于1号连通分量，则belong[1]=1; bool inStack[MAXN];//记录节点是否出栈 int DFN[MAXN];//记录在栈中的位置;记录节点是否被访问 int LOW[MAXN];//记录某节点与栈中的那个节点相关联 int index=0;//全局变量，用来记录次序。 void tarjan(int t){ s.push(t); DFN[t] = LOW[t] = index++; inStack[t] = true; //节点t入栈 s.push(t); int j; for(j = 0 ;j < graph[t].size();j++){ if(!DFN(graph[t][j])){ //如果之前没有访问过，DFN两个功能，1.记录访问的时间戳2.是否访问过 tarjan(graph[t][j]);//DFS,深度优先遍历 //遍历结束之后，当前节点的LOW值应该去其中的最小值。 if(LOW[t]>LOW[graph[t][j]]) LOW[t]=LOW[graph[t][j]]; }else{ //如果该节点已经访问过，就需要查看该节点是否存在与栈中 if(inStack[graph[t][j]]) //如果存在，则更新当前节点的LOW值，取两者的最小值 LOW[t] = min(LOW[t],DFN[graph[t][j]]); } } //当所有的子节点都遍历完了 if(DFN(t)==LOW[t]){ typeNum++; int temp; do{ temp = s.top(); s.pop(); inStack[temp] = false; belong[temp] = typeNum; }while(temp!=t); } } //代码采用vector来储存图的节点信息， //主函数没有去读图的信息，所以不能运行。 int main() { int n; cin>>n; int i; for(i =1 ;i<=n;i++){ if(!DFN[i]){ tarjan(i); } } return 0; }

LCA

最近公共祖先问题。

问题描述

如下图所示，节点7和8的最近公共祖先为5，节点4和节点7的LCA为2,节点4和节点3的LCA为1。

LCA问题就是，给定一棵树如图所示，求若干顶点对的最近公共祖先。LCA问题有离线和在线算法。trajan算法为离线算法。离线算法的意思就是在操作之前需要知道查询那些点对的LCA，然后通过DFS遍历树，为节点添加一些属性，来计算LCA。

伪代码

void LCS(int root) for 对于所有与root相连的有向边i LCS（i）；//DFS深度优先遍历 parent[i]=root; root节点标记为已访问； for 所有需要与root节点计算LCS的j if j节点以及访问 ans=find(j)//利用并查集的find函数思想，找到LCS,也就是ans

实例分析

问题：寻找(4,7),(7,8),(4,6),(7,6)三组的LCS

1.深度优先遍历。 从LCS(1)->LCS(2)->LCS(4)。到LCS(4)的时候，由于没有子节点，所以直接标记节点4已经访问，需要查询的节点也都还没访问，所以LCS(4)返回，然后调回LCS(2)，在LCS(2)中令p[4]=2；

2.继续访问子节点 在LCS(2)中，继续访问节点2的子节点5，LCS(5)->LCS(7);因为LCS(7)没有子节点，所以直接标记节点7已经访问。然后发现（4,7）两个节点都是已经访问的。所以ans(4,7)=find(4)=2; 注：并查集中的find(i)函数，是一直向上找i的parent节点，直到parent节点的父节点为0为止，所以find(4)=2。

3.继续回溯到节点5，访问节点8，执行LCS(8),节点8没有子节点，于是直接标记节点8已访问。同理可知ans(7,8)=find(7)=5;此时LCS(8)执行完毕，于是回溯到节点5（LCS(5)）;使得p[8] = 5;节点5没有子节点访问结束，于是标记节点5已访问，没有要查询的，直接返回到LCS(2);节点2的子节点访问结束，标记节点2为已访问，直接返回LCS(2)到LCS(1)；标记p[2] =1。

4.继续访问1的子节点LCS(3)->LCS(6)。在LCS(6)中计算(4,6),和(7,6);ans(4,6)=find(4)=1;ans(6,7)=find(7)=1;于是继续回溯到3，到1，算法就结束了。

代码实现

代码没有执行，只有思想，不保证正确。

//并查集的find函数 int find(int i){ if(parent[i]!=0){ return find(parent[i]); }else return i; } void LCS(int root){ int j; for(j = 0;j<tree[root].size();j++){ LCS(tree[root][j]);//深度搜索 parent[tree[root][j]] =root;//搜索结束，标记其父节点 } visited[root] = 1;//标记为已经访问 int start = root; int i; for(i = 0;i<query[start].size();i++){//对于所有需要查询的(start，i) if(visited(query[start][i])){ LowCS[start][query[start][i]] = find(start);//用来储存父节点 } } }

实例

牛客网上的小米git 题目描述： git是一种分布式代码管理工具，git通过树的形式记录文件的更改历史，比如： base’<–base<–A<–A’ ^ | — B<–B’ 小米工程师常常需要寻找两个分支最近的分割点，即base.假设git 树是多叉树，请实现一个算法，计算git树上任意两点的最近分割点。 （假设git树节点数为n,用邻接矩阵的形式表示git树：字符串数组matrix包含n个字符串，每个字符串由字符’0’或’1’组成，长度为n。matrix[i][j]==’1’当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。） 输入： [01011,10100,01000,10000,10000],1,2 输出：1

代码实现

/*============================================================================ Name : git.cpp Author : SELOUS Version : Copyright : Your copyright notice Description : LCS ============================================================================ */ #include <iostream> using namespace std; #include <vector> #include <string> #include<cstring> #include <cstdlib> #define MAXNUM 20 vector <string> graph;//用来储存图的信息 int indexA; int indexB; int parent[MAXNUM]; bool visited[MAXNUM];//是否访问 bool par[MAXNUM];//标记其子节点是否都访问过，没有用visited代替，是因为他储存的时候用的是无向图储存的树结构 void init(){ memset(parent,-1,sizeof(parent)); memset(visited,0,sizeof(visited)); memset(par,0,sizeof(par)); } /*并查集的find函数*/ int find(int root){ if (parent[root]!=-1){ return find(parent[root]); } return root; } /* * input: * t:深度优先便利的起始节点 * n:节点个数*/ void targan(int t,int n){ visited[t] = 1; int i; for(i=0;i<n;i++){ char next = graph[t].c_str()[i]; if(next=='1'&&!visited[i]){ targan(i,n); parent[i]=t; } } par[t] = 1; if(t==indexA){ if(par[indexB]){ cout<<find(indexB); } }else if(t==indexB){ if(par[indexA]){ cout<<find(indexA); } } } int main() { int n; cin>>n>>indexA>>indexB; int i; string str; for(i=0;i<n;i++){ cin>>str; graph.push_back(str); } // Solution s; // cout<<s.getSplitNode(graph,indexA,indexB); init(); targan(0,n); return 0; }

博客

1.解析强连通比较好的博客 ——2017.3.9