[关闭]
@zzzc18 2017-05-12T12:12:36.000000Z 字数 2071 阅读 532

两种LCA

LCA


LCA两种方法

  1. 在线:倍增
  2. 离线:Tarjan

倍增

  1. #include<cstdio>
  2. #include<cmath>
  3. #define MAXN 700000+900
  4. #define MAXM 1200000+900
  5. using namespace std;
  6. int anc[MAXN][33];
  7. int n,m,root;
  8. struct E{
  9. int next,to;
  10. }edge[MAXM];
  11. int head[MAXN],edge_num;
  12. int depth[MAXN];
  13. int logn;
  14. void SWAP(int &x,int &y){
  15. int t=x;x=y;y=t;
  16. }
  17. void addedge(int x,int y){
  18. edge[++edge_num].next=head[x];
  19. edge[edge_num].to=y;
  20. head[x]=edge_num;
  21. }
  22. void DFS(const int &x,const int &y){
  23. int i;
  24. for(i=head[x];i;i=edge[i].next){
  25. if(edge[i].to!=y){
  26. anc[edge[i].to][0]=x;
  27. depth[edge[i].to]=depth[x]+1;
  28. DFS(edge[i].to,x);
  29. }
  30. }
  31. }
  32. void PRE(){
  33. int i,j;
  34. for(i=1;(1<<i)<=n;i++){
  35. for(j=1;j<=n;j++){
  36. if(anc[j][i-1]){
  37. anc[j][i]=anc[anc[j][i-1]][i-1];
  38. }
  39. }
  40. }
  41. }
  42. int LCA(int x,int y){
  43. if(depth[x]<depth[y])
  44. SWAP(x,y);
  45. int i,j;
  46. for(i=logn;i>=0;i--){
  47. if(depth[y]+(1<<i)<=depth[x])
  48. x=anc[x][i];
  49. }
  50. if(x==y) return x;
  51. for(i=logn;i>=0;i--){
  52. if(anc[x][i] && anc[x][i]!=anc[y][i]){
  53. x=anc[x][i];y=anc[y][i];
  54. }
  55. }
  56. return anc[x][0];
  57. }
  58. int main(){
  59. scanf("%d%d%d",&n,&m,&root);
  60. int i;int a,b;
  61. for(i=1;i<n;i++){
  62. scanf("%d%d",&a,&b);
  63. addedge(a,b);addedge(b,a);
  64. }
  65. DFS(root,0);
  66. PRE();
  67. logn=floor(log(n)/log(2));
  68. for(i=1;i<=m;i++){
  69. scanf("%d%d",&a,&b);
  70. printf("%d\n",LCA(a,b));
  71. }
  72. return 0;
  73. }

Tarjan

方法:DFS,从最下层把节点加入并查集,如果询问的两个端点都出现在并查集中(首次),就可以记录答案啦,就是并查集中的fa

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define MAXN 600000
  4. using namespace std;
  5. struct E{
  6. int next,to,id;
  7. }edge[2*MAXN],ask[2*MAXN];
  8. int head[MAXN],edge_num,h1[MAXN],a_num;
  9. int root;
  10. bool vis[MAXN];
  11. int fa[MAXN];
  12. int ans[MAXN];
  13. int n,m;
  14. void addedge(int x,int y){
  15. edge[++edge_num].next=head[x];
  16. edge[edge_num].to=y;
  17. head[x]=edge_num;
  18. }
  19. void addask(int x,int y,int z){
  20. ask[++a_num].next=h1[x];
  21. ask[a_num].to=y;
  22. ask[a_num].id=z;
  23. h1[x]=a_num;
  24. }
  25. int Find(int x){
  26. if(fa[x]!=x) fa[x]=Find(fa[x]);
  27. return fa[x];
  28. }
  29. void LCA(int x){
  30. int i;
  31. vis[x]=1;
  32. for(i=head[x];i;i=edge[i].next){
  33. if(!vis[edge[i].to])
  34. LCA(edge[i].to),fa[edge[i].to]=x;
  35. }
  36. for(i=h1[x];i;i=ask[i].next){
  37. if(vis[ask[i].to])
  38. ans[ask[i].id]=Find(ask[i].to);
  39. }
  40. }
  41. int main(){
  42. scanf("%d%d%d",&n,&m,&root);
  43. int i;int a,b;
  44. for(i=1;i<=n-1;i++){
  45. scanf("%d%d",&a,&b);
  46. addedge(a,b);
  47. addedge(b,a);
  48. }
  49. for(i=1;i<=m;i++){
  50. scanf("%d%d",&a,&b);
  51. addask(a,b,i);addask(b,a,i);
  52. }
  53. for(i=1;i<=n;i++)
  54. fa[i]=i;
  55. LCA(root);
  56. for(i=1;i<=m;i++)
  57. printf("%d\n",ans[i]);
  58. return 0;
  59. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注