tarjan求lca ：并查集+dfs

//参考博客 https://www.cnblogs.com/jsawz/p/6723221.html#include<bits/stdc++.h> using namespace std; #define maxn 420000 struct Query{int to,nxt,lca;}q[maxn]; struct Edge{int to,nxt;}edge[maxn<<1]; int n,m,p,x,y,tot_e,tot_q,head_q[maxn],head_e[maxn]; int fa[maxn],vis[maxn]; void init(){ memset(head_e,-1,sizeof head_e); memset(head_q,-1,sizeof head_q); memset(fa,-1,sizeof fa); tot_q=tot_q=0; } void addedge(int u,int v){ edge[tot_e].to=v;edge[tot_e].nxt=head_e[u];head_e[u]=tot_e++; } void addquery(int u,int v){ q[tot_q].to=v;q[tot_q].nxt=head_q[u];head_q[u]=tot_q++; } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} int dfs(int u){ fa[u]=u;vis[u]=1; for(int i=head_e[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(vis[v])continue; dfs(v);fa[v]=u; } for(int i=head_q[u];i!=-1;i=q[i].nxt){ int v=q[i].to; if(vis[v]) q[i].lca=q[i^1].lca=find(v); } } int main(){ init(); cin>>n>>m>>p; for(int i=1;i<n;i++){ cin>>x>>y; addedge(x,y); addedge(y,x); } for(int i=0;i<m;i++){ cin>>x>>y; addquery(x,y); addquery(y,x); } dfs(p); for(int i=0;i<m;i++) printf("%d ",q[i<<1].lca); }

 

转载于:https://www.cnblogs.com/zsben991126/p/10356599.html

相关资源：各显卡算力对照表！