首页 > 代码库 > Tarjan--LCA算法的个人理解即模板
Tarjan--LCA算法的个人理解即模板
tarjan---LCA算法的步骤是(当dfs到节点u时):
实际： 并查集+dfs
具体步骤：
1 在并查集中建立仅有u的集合,设置该集合的祖先为u
1 对u的每个孩子v:
1.1 tarjan之
1.2 合并v到父节点u的集合,确保集合的祖先是u
2 设置u为已遍历
3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先。
举例子：
假设遍历完10的孩子,要处理关于10的请求了
取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10
集合的祖先便是关键路径上距离集合最近的点
比如此时:
1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
3,7为一个集合,祖先为3,集合中点和10的LCA为3
8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
10,12为一个集合,祖先为10,集合中点和10的LCA为10
你看,集合的祖先便是LCA吧,所以第3步是正确的
道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点
此段话语来自sre="http://purety.jp/akisame/oi/TJU/"
模板：
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 5 const int MAX=10001; 6 int father[MAX]; 7 int rank[MAX]; 8 int indegree[MAX];//保存每个节点的入度 9 int visit[MAX]; 10 vector<int> tree[MAX],Qes[MAX]; 11 int ancestor[MAX]; 12 13 14 void init(int n) 15 { 16 for(int i=1;i<=n;i++) 17 { 18 19 rank[i]=1; 20 father[i]=i; 21 indegree[i]=0; 22 visit[i]=0; 23 ancestor[i]=0; 24 tree[i].clear(); 25 Qes[i].clear(); 26 } 27 28 } 29 30 int find(int n) 31 { 32 if(father[n]==n) 33 return n; 34 else 35 father[n]=find(father[n]); 36 return father[n]; 37 }//查找函数，并压缩路径 38 39 int Union(int x,int y) 40 { 41 int a=find(x); 42 int b=find(y); 43 if(a==b) 44 return 0; 45 //相等的话,x向y合并 46 else if(rank[a]<=rank[b]) 47 { 48 father[a]=b; 49 rank[b]+=rank[a]; 50 } 51 else 52 { 53 father[b]=a; 54 rank[a]+=rank[b]; 55 } 56 return 1; 57 58 }//合并函数，如果属于同一分支则返回0，成功合并返回1 59 60 61 void LCA(int u) 62 { 63 ancestor[u]=u; 64 int size = tree[u].size(); 65 for(int i=0;i<size;i++) 66 { 67 LCA(tree[u][i]); 68 Union(u,tree[u][i]); 69 ancestor[find(u)]=u; 70 } 71 visit[u]=1; 72 size = Qes[u].size(); 73 for(int i=0;i<size;i++) 74 { 75 //如果已经访问了问题节点,就可以返回结果了. 76 if(visit[Qes[u][i]]==1) 77 { 78 cout<<ancestor[find(Qes[u][i])]<<endl; 79 return; 80 } 81 } 82 } 83 84 85 int main() 86 { 87 int cnt; 88 int n; 89 cin>>cnt; 90 while(cnt--) 91 { 92 cin>>n;; 93 init(n); 94 int s,t; 95 for(int i=1;i<n;i++) 96 { 97 cin>>s>>t; 98 tree[s].push_back(t); 99 indegree[t]++;100 }101 //这里可以输入多组询问102 cin>>s>>t;103 //相当于询问两次104 Qes[s].push_back(t);105 Qes[t].push_back(s);106 for(int i=1;i<=n;i++)107 {108 //寻找根节点109 if(indegree[i]==0)110 {111 LCA(i);112 break;113 }114 }115 }116 return 0;117 }
Tarjan--LCA算法的个人理解即模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。