- 1Elasticsearch(ES) 添加/更新映射
- 2element ui el-avatar 源码解析零基础逐行解析
- 3Android Studio配置优化最全详解_android studio的sdk tools展示全部的内容
- 4SUPPORTS， REQUIRED ，REQUIRES_NEW的区别_required supports
- 5Git管理神器SourceTree使用教程详解（连接远程仓库，克隆，拉取，提交，推送，新建/切换/合并分支，冲突解决，提交PR）...
- 6android视频开发倍速播放，调整视频播放速度_安卓开发视频播放器实现倍速播放
- 7python爬虫开发之“智联招聘”网页爬取_基于python的网络爬虫(智联招聘)开发与实现
- 8MySQL_02 (图形化界面 )_mysql图形化界面
- 9python爬取网易云音乐热评_网易云热评爬取
- 10（已解决）word如何制作和引用参考文献_csdnword里面参考文件怎么引用
LCA算法以及原理详解
赞
踩
LCA-最近公共祖先
LCA(Least Common Ancestors)，即最近公共祖先，这种描述是基于树结构的，也即我们通通常只在树结构中考虑祖先问题。树实际上就是图论中的有向无环图，而要研究LCA问题，首先我们要指定树中的一个顶点为根节点，并以该节点遍历有向无环图，生成一颗DFS序下的树，假设我们要查询的两个节点为u,v，DFS序下根节点到两点的最短路径分别是(r,u),和(r,v)，LCA就是(r,u)与(r,v)公共路径的最后一个节点，如下图所示，w即为LCA。
换句话说，u,v的LCA就是以r为根的树中，u到v的最短路径中深度最小的点（假设根节点的深度为1，而深度是往下递增的）。
暴力
暴力法求解一对节点的LCA时时间复杂度是O(n)的，所以当查询多对节点的LCA时，暴力算法的时间复杂度往往不满足要求。
暴力法就是通过不断地将深度较深的点往上求父节点，直到两个点的父节点重合时，即可得到LCA。下面给出一种实现方法。
int dfs1(int k,int u,int v){//暴力法1的dfs方法,u,v为要查询的两个节点 int count=0; int ans=-1; for(int i=0;i<g[k].size();i++){ if(!color[g[k][i]]){ color[g[k][i]]=1; int num=dfs1(g[k][i],u,v); if(num>=0){ count++; ans=num; } } } //如果有两个分支返回返回的是节点编号，那么此时该节点一定是LCA，返回节点编号 if(count==2)ans=k; //遍历到u,或者v时，返回该点编号即可 if(k==u||k==v)ans=k; //否则返回-1，也即不返回任何节点编号 return ans; } int violence1(int u,int v){ memset(color,0,sizeof(color)); return dfs1(0,u,v);//假设根节点为0 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
倍增算法
倍增法其实就是每一步尽可能跳的多一点，他的思想与二分的想法其实是一致的，假设我们要求解LCA(u,v)，暴力的想法是我们始终将深度较深的往上跳跃一步，直到u,v的深度第一次相等时，此时该节点就是LCA(u,v)，但是这样做的话，在一个接近线性的树中，时间复杂度是O(n）的，当有多组查询时，这种开销就无法承受了。
倍增的原理是每一次尽可能地多跳一些步数，而不是一步一步往上跳，当时如何快速找到应该跳的步数呢？考虑到depth[LCA(u,v)]-depth[u]是一个深度差值，而一开始我们是不知道LCA（u，v）到底是哪一个节点，并且u和v也可能不在同一深度，那么为了便于计算，我们应该首先间u和v调整到同一深度。
当u和v的深度相同时，此时depth[LCA(u,v)]-depth[u]=depth[LCA(u,v)]-depth[v]，也即u和v跳相同的步数即可到达最近公共祖先。由于此时不知道LCA（u,v）到底是哪一个，所以此时跳跃的步数只能使尝试性的，否则我们可能会直接跳过头，那么什么样的尝试序列是比较好的呢？考虑到搜索算法的时间复杂度上限，我们可以选择跳跃2^j步进行尝试。
但是这里面存在一个问题就是，当u和v跳跃2^j步后，两者的祖先相等，此时该节点就是u和v的一个公共祖先，但是却不一定是最近公共祖先，所以为了避免这种情况的出现，我们选择u和v跳跃2 ^j步后，两者的祖先不是公共祖先的最大j，进行跳跃；跳跃2 ^j步后，此时u,v依然在同一深度，与之前的子问题是等价的，我们可以继续该操作，直到j==0跳出循环；由于我们每一步都不会直接跳到最近公共祖先，所以最后得到的结果中，u和v都跳跃到了最近公共祖先的下一层，此时我们直接返回u或者v的父节点即可。
上述跳跃2 ^j的操作是通过一个dp数组来实现的，我们用dp[i][j]表示节点i的第2 ^j个祖先，那么dp[i][j]可以由更小的子问题推导出，显然我们可以得到dp[i][j]=dp[dp[i][j-1]][j-1];这样我们在遍历到每一个节点是预处理出以该节点的所有可能的dp值即可。初始化时dp[i][0]其实就是i的父节点，我们可以直接在遍历的时候赋值。
下图是该算法每一次尝试跳跃时所做的选择。
例题
#include<bits/stdc++.h> using namespace std; //LCA算法复习 //动态规划+倍增优化 const int N=1000010; int edge[N]; int nest[N]; int last[500010]; int cnt=1; inline void add(int u,int v){ nest[cnt]=last[u]; edge[cnt]=v; last[u]=cnt; cnt++; return; } //用来保存父节点 int dp[500010][20]; //保存深度 int depth[500010]; //预处理出父亲切点 bool vise[500010]; void DFS(int k){ //预处理出DP数组 for(int i=1;(1<<i)<depth[k];i++){ dp[k][i]=dp[dp[k][i-1]][i-1]; } for(int i=last[k];i;i=nest[i]){ //求解直接公共祖先； if(vise[edge[i]])continue; vise[edge[i]]=true; depth[edge[i]]=depth[k]+1; dp[edge[i]][0]=k; DFS(edge[i]); } return; } int lca(int u,int v){ if(depth[u]<depth[v])swap(u,v); //弹节点 int k=log2(depth[u]-depth[v]); for(int i=k;i>=0;i--){ if(depth[dp[u][i]]>=depth[v])u=dp[u][i]; } if(u==v)return u; //查询 k=log2(depth[u]); for(int i=k;i>=0;i--){ if(dp[u][i]==dp[v][i])continue; u=dp[u][i]; v=dp[v][i]; } return dp[u][0]; } int main(){ //LCA模板题 int n,m,s; cin>>n>>m>>s; int u,v; for(int i=0;i<n-1;i++){ scanf("%d %d",&u,&v); add(u,v); add(v,u); } //这里要初始化为1，避免与深度为0的0产生歧义。 depth[s]=1; vise[s]=true; DFS(s); for(int i=0;i<m;i++){ scanf("%d %d",&u,&v); cout<<lca(u,v)<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
上述算法的预处理时间复杂度是O(nlogn)，每次查询时间是O(logn)的。总的时间复杂度是O(nlon+mlogn)的；其中m为查询次数。
注：上述算法主要有三个核心部分①中序前序遍历建立兄弟链表法的二叉树结构；②DFS获得预处理数据；③倍增法查询LCA。
ST算法
看了一下网上的博客，解释的也不是很清楚，只是给出了一个DFS序，然后给出了实现代码，但是并没有实质上的原理阐述，而我根据我的理解对该算法进行解读吧。
要想理解一般树的LCA算法，我觉得首先要理解二叉树的LCA算法，二叉树中由于每个节点只有两个孩子，假设我们要求解LCA的两个节点为u和v，考虑到在二叉树的中序遍历中有这样一个特性，也即u和v的LCA，一定在u和v之间遍历，而u和v的其他非LCA祖先，一定在u和v遍历次序之外，也即假设由中序遍历次序…u…v…，那么LCA(u,v)一定在u,v中间，也即有…u…LCA(u,v)…v…，而LCA(u,v)的祖先节点则一定在v之后遍历。
这样，如果我们可以发现一个区间[u,v]中LCA(u,v)具有的特性，即可快速找到该点，考虑到区间[u,v]中（我们考虑的是中序遍历中的遍历区间）；LCA(u,v)的深度是最小的，那么如果我们可以快速得到区间[u,v]中的最小值即可求解出LCA(u,v)了；
显然对于数组区间最值查询问题我们可以借用ST算法或者线段树实现，这里不再介绍这两种算法的时间过程，感兴趣可以看我的另一篇博客；
上述思想实际上是在二叉树里面实现的，由于二叉树每个节点最多只有两个子节点，所以我们有中序遍历的说法，但是实际上一般树中是不存在中序遍历的， 我们通常只有DFS的遍历方式，那么如何在一般树中达到上述结构描述的性质呢？我们上述算法中要查询LCA(u,v)时，默认了LCA(u,v)一定在区间[u,v]中，而通常的DFS却不能保证这个性质，为了达到上述效果，我们需要保证我们在一般树中得到的遍历序列中，父节点的任意两个孩子之间都有父节点存在；
为了达到上述效果，我们可以冗余存储，也即每当我们遍历到当前节点的一个分支时，我们就将当前节点也添加进去，这样我们就可以保证任意两个孩子节点都有一个父节点存在了，那么我们就可以按照二叉树中的思想求解LCA算法了。
例题1
#include<bits/stdc++.h> using namespace std; const int N=5000005; //兄弟链表法存储所有边 int edge[2*N]; int nest[2*N]; int last[N]; int cnt=1; inline void add(int u,int v){ nest[cnt]=last[u]; edge[cnt]=v; last[u]=cnt; cnt++; return; } int sq[2*N]; int d[N]; bool vise[N]; int has[N]; void DFS(int k){ for(int i=last[k];i;i=nest[i]){ if(vise[edge[i]])continue; vise[edge[i]]=true; d[edge[i]]=d[k]+1; DFS(edge[i]); sq[++cnt]=edge[i]; has[edge[i]]=cnt; sq[++cnt]=k; } return; } int dp[2*N][20]; int lca(int l,int r){ if(l>r)swap(l,r); int k=log2(r-l+1); if(d[dp[l][k]]<d[dp[r-(1<<k)+1][k]]){ return dp[l][k]; }else{ return dp[r-(1<<k)+1][k]; } } int main(){ int n,m,s; cin>>n>>m>>s; int u,v; for(int i=0;i<n-1;i++){ scanf("%d %d",&u,&v); add(u,v); add(v,u); } cnt=0; vise[s]=true; d[s]=1; DFS(s); for(int i=0;i<=cnt;i++)dp[i][0]=sq[i]; for(int j=1;j<=20;j++){ for(int i=0;i+(1<<j)<=cnt+1;i++){//这里一定要考虑区间的边界，要满足超出区间右侧一位 if(d[dp[i][j-1]]<d[dp[i+(1<<j-1)][j-1]]){ dp[i][j]=dp[i][j-1]; }else{ dp[i][j]=dp[i+(1<<j-1)][j-1]; } } } has[s]=cnt; for(int i=0;i<m;i++){ scanf("%d %d",&u,&v); cout<<lca(has[u],has[v])<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
例题2
#include<bits/stdc++.h> using namespace std; //LCA ST算法实现 #define N 100001 int ins[N]; int mid[N]; unordered_map<int,int> has;//构建二叉树时，用于寻找中序遍历中节点的位置 unordered_map<int,int> tran;//节点编码，编码到1到N的自然数上 unordered_map<int,int> retran;//解码，返回原始的输入数据 int edge[2*N][2]; int last[N]; int id=0; //添加边 inline void add(int u,int v){//添加边，一定要记住 edge[id][0]=last[u]; edge[id][1]=v; last[u]=id; id++; edge[id][0]=last[v]; edge[id][1]=u; last[v]=id; id++; return; } void dfs(int l,int r,int pre,int later,int k){ if(k>0)add(k,ins[l]); if(l==r)return; int index=has[ins[l]]; int dis=index-pre; if(dis>=1)dfs(l+1,l+dis,pre,index-1,ins[l]); if(l+dis+1<=r)dfs(l+dis+1,r,index+1,later,ins[l]); return ; } //arr中存的是深度，而ans中存的是节点的坐标 int arr[2*N]; int ans[2*N]; int dep[N]; int first[N]; int cnt=0; void DFS(int k){ for(int i=last[k];i!=-1;i=edge[i][0]){ if(dep[edge[i][1]]==0){ dep[edge[i][1]]=dep[k]+1; DFS(edge[i][1]); first[edge[i][1]]=cnt; arr[cnt]=dep[edge[i][1]]; ans[cnt]=edge[i][1]; cnt++; //每遍历一次子树，就将父节点添加一次 arr[cnt]=dep[k]; ans[cnt]=k; cnt++; } } return ; } int main(){ int m,n; cin>>m>>n; //重映射，数据中给出的节点的值，而不是序号，这里随便指定一个序号。 for(int i=0;i<n;i++)cin>>mid[i]; for(int i=0;i<n;i++)cin>>ins[i]; for(int i=0;i<n;i++){ tran[ins[i]]=i+1; retran[i+1]=ins[i]; } for(int i=0;i<n;i++)ins[i]=tran[ins[i]]; for(int i=0;i<n;i++)mid[i]=tran[mid[i]]; for(int i=0;i<n;i++)has[mid[i]]=i; memset(last,-1,sizeof(last));//last是一定要初始化为-1的，否则无法DFS dfs(0,n-1,0,n-1,0); //初始化第一个位置 memset(dep,0,sizeof(dep)); memset(ans,0,sizeof(ans)); dep[ins[0]]=1; DFS(ins[0]);//生成一个特殊的DFS序列 //注意单独处理出根节点的first数组,由于最后一个一定是根节点，所以我们直接将first设置为cnt-1即可 first[ins[0]]=cnt-1; //预处理ST算法的DP数组 int dp[cnt][(int)log2(cnt)+1]; for(int i=0;i<cnt;i++)dp[i][0]=i;//保存的是下标 //C++当数组开辟空间不够时，会占用重写已经开辟的空间，造成不可预知的错误 //一定有一个最值 for(int i=1;(1<<i)<cnt;i++){ for(int j=0;j+(1<<i)-1<cnt;j++){ if(arr[dp[j][i-1]]<arr[dp[j+(1<<i-1)][i-1]]){ dp[j][i]=dp[j][i-1]; }else{ dp[j][i]=dp[j+(1<<i-1)][i-1]; } } } for(int i=0;i<m;i++){ int u,v; cin>>u>>v; int a=tran[u]; int b=tran[v]; bool tag=false; if(a==0){ cout<<"ERROR: "<<u; tag=true; } if(b==0){ if(tag){ cout<<" and "<<v<<" are not found."<<endl; continue; }else{ cout<<"ERROR: "<<v<<" is not found."<<endl; continue; } } if(tag){ cout<<" is not found."<<endl; continue; } bool tip=false; if(first[a]>first[b]){ swap(a,b); swap(u,v); tip=true; } int f; int k=log2(first[b]-first[a]+1); if(arr[dp[first[a]][k]]<arr[dp[first[b]-(1<<k)+1][k]]){ f=ans[dp[first[a]][k]]; }else{ f=ans[dp[first[b]-(1<<k)+1][k]]; } if(f==a){ cout<<u<<" is an ancestor of "<<v<<"."<<endl; continue; } if(f==b){ cout<<v<<" is an ancestor of "<<u<<"."<<endl; continue; } if(!tip)cout<<"LCA of "<<u<<" and "<<v<<" is "<<retran[f]<<"."<<endl; else cout<<"LCA of "<<v<<" and "<<u<<" is "<<retran[f]<<"."<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
上述是LCA的ST算法实现方式，主要原理便是我上面所描述的，但是实际上针对本题可以简化DFS生成序列的过程，因为二叉树本身的中序遍历已经有了，我们只需要求出每个节点的深度即可运用ST算法。
tarjan算法
终于到了最后的tarjan算法，断断续续也写了好几天了，现在来讲一讲tarjan的原理，刚开始看这个算法时，我觉得相比于倍增和ST算法来说是更难理解的，因为没有那种迸发的灵感，上面两个想法其实一开我就有一些想法的，只是有一些细节上有所缺失，但是当了解关键点以后，还是可以很轻易理解的，而tarjan算法一开始给我的感觉就是很乱，就像是做数学题要分类讨论，而我脑子里却一团糟的感觉。
但是仔细梳理以后还是发现了该算法的神奇之处，实际上好的讲解也可以比较轻松的理解该算法的，好了，废话不多说了，直接上干货。
首先还是要分析一下我们图算法里面最核心的知识——遍历，我们考虑DFS后序遍历时的特点（也即先遍历孩子节点，再遍历当前节点），对于两个节点u，v来说，他们要么在最近公共祖先的两个子树中，要么就是其中一个是祖先节点，一个是子孙节点。而DFS遍历时，我们遍历到u以及v时具有什么特殊的性质呢？
如果u是先遍历到的，此时由于不知道v的信息，所以我们也无法对最近公共祖先做出判断。但是如果u是后遍历到的， 而v是先遍历到的，那么u遍历结束后，在DFS递归的返回过程中，u一定会不断向上返回，只到某一刻返回到u和v的LCA节点，那么我们如何快速知晓这个节点到底是哪一个呢？考虑到LCA(u,v)一定在u，v的上层，而如果我们将LCA(u,v)的v所在的子树内部的LCA问题都处理结束后，我们其实可以将这个子树中点集视为一个点，因为该子树中所有节点与子树之外节点的LCA只能是LCA(u,v)本身或者LCA(u,v)的父节点了。那么当我们将这个集合中每个点的父节点都设置为LCA(u,v)，在探查到u时，我们就可以通过v的父节点快速获得LCA(u,v)的值。
对于将集合中每一个点的父节点都设置为LCA(u,v)的过程，我们可以使用并查集来实现，因为这是一个一个的子问题；当某一个节点s的所有分支的节点的可处理LCA问题都处理结束后，此时s的子树和s已经是一个并查集了，并且并查集的根节点是s，当s也处理结束后，我们可以直接将s并在其父节点的并查集中，并且将其父节点设置为根节点。这样后续节点与s以及s子树中节点的LCA问题的父节点只可能是s的祖先节点，而不可能是s或者s的子孙节点。而后续节点要想快速查询到与已经遍历过某个顶点的LCA时，直接查询已经遍历过顶点所在并查集的根节点即可。而查到的根节点一定是LCA，因为根节点总是后于要查询节点处理结束的。
例题1
#include<bits/stdc++.h> using namespace std; //tarjan离线算法实现LCA const int N=5000005; int arr[N]; int find(int x){ return x==arr[x]?x:arr[x]=find(arr[x]); } //这里的merge不能用秩平衡定理 void merge(int x,int y){ x=find(x); y=find(y); arr[x]=y; return; } //兄弟链表法存储所有边 int edge[2*N]; int nest[2*N]; int last[N]; int cnt=1; inline void add(int u,int v){ nest[cnt]=last[u]; edge[cnt]=v; last[u]=cnt; cnt++; return; } //用来存储所有的查询以及查询的序号 vector<int> q[N]; vector<int> qi[N]; void add_query(int u,int v,int id){ q[u].push_back(v); q[v].push_back(u); qi[u].push_back(id); qi[v].push_back(id); return; } int vise[N]; int ans[N]; void DFS(int k){ //初次访问 vise[k]=1; for(int i=last[k];i;i=nest[i]){ if(vise[edge[i]])continue; DFS(edge[i]); //注意这里只能单向合并，可以直接设置父节点 merge(edge[i],k); } //这里一定要注意遍历顺序是后根序。 //查看是否已经有可以求解的 for(int i=0;i<q[k].size();i++){ if(vise[q[k][i]]==2){ ans[qi[k][i]]=find(q[k][i]); } } //遍历结束 vise[k]=2; return; } int main(){ int n,m,s; cin>>n>>m>>s; //初始化并查集 for(int i=1;i<=n;i++)arr[i]=i; int u,v; for(int i=0;i<n-1;i++){ scanf("%d %d",&u,&v); add(u,v); add(v,u); } for(int i=0;i<m;i++){ scanf("%d %d",&u,&v); add_query(u,v,i); } DFS(s); for(int i=0;i<m;i++){ cout<<ans[i]<<endl; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
例题2
#include<iostream> #include<vector> #include<string.h> using namespace std; #define N 100001 int arr[N]; int find(int x){ return x==arr[x]?x:arr[x]=find(arr[x]); } void merge(int x,int y){ arr[x]=y; return ; } int edge[N*2][2]; int last[N]; int id=0; void add(int u,int v){ edge[id][0]=last[u]; edge[id][1]=v; last[u]=id; id++; return ; } int vise[N]; int ans=0; int a=0,b=0; void DFS(int k){ for(int i=last[k];i!=-1;i=edge[i][0]){ if(vise[edge[i][1]]==0){ DFS(edge[i][1]); if(a==edge[i][1]&&vise[b]==1){ ans=find(b); } if(b==edge[i][1]&&vise[a]==1){ ans=find(a); } vise[edge[i][1]]=1; merge(edge[i][1],k);//并查集中将父节点设置为根，便于后续查询，这里是并查集变种 //由于我们使用了路径压缩，实际上时间复杂度是较低的。 } } return; } int main(){ std::ios::sync_with_stdio(false); int T; cin>>T; for(int i=0;i<T;i++){ int n; cin>>n; int tip[N]; int u,v; memset(tip,0,sizeof(tip)); memset(last,-1,sizeof(last));//一定要初始化 //初始化并查集 for(int i=1;i<=n;i++)arr[i]=i; for(int i=0;i<n-1;i++){ cin>>u>>v; add(u,v); tip[v]=true; } cin>>a>>b; for(int i=1;i<=n;i++){ if(tip[i]==0){ memset(vise,0,sizeof(vise)); DFS(i); break; } } cout<<ans<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
