参考 https://comzyh.com/blog/archives/492/ Tarjan算法 利用离线的方法求 LCA 复杂度o(n+2q) (离线来做复杂度还是很可观的
查询两点距离的功能之后在补上吧
#include<cstdio> #include<cstring> using namespace std; const int MAXN=1e5+5; struct node{int to,cost,next;};struct NODE{int to,next;}; NODE que[MAXN<<1];node dat[MAXN<<1];int pit[MAXN],p[MAXN],par[MAXN],vis[MAXN],LCA[MAXN],u,o; inline void add_edge(int x,int y,int cost){ dat[u]=(node){y,cost,pit[x]};pit[x]=u++; dat[u]=(node){x,cost,pit[y]};pit[y]=u++; } inline void add_edge(int x,int y){ que[o]=(NODE){y,p[x]};p[x]=o++; que[o]=(NODE){x,p[y]};p[y]=o++; } /*** 以下为主要部分 **/ inline void init(int n){for(int i=0;i<=n;i++) par[i]=i;} int find(int x){return x==par[x]?x:par[x]=find(par[x]);} void lca(int v){ vis[v]=true; for(int i=p[v];i;i=que[i].next){ NODE &e=que[i]; if(vis[e.to]){ LCA[(i+1)>>1]=find(e.to); } } for(int i=pit[v];i;i=dat[i].next){ node &e=dat[i]; if(vis[e.to]) continue; lca(e.to); par[e.to]=v; } } int main() { int V,E,Q; while(scanf("%d%d%d",&V,&E,&Q)!=EOF){ init(V); memset(pit,0,sizeof(pit)); u=1; memset(p,0,sizeof(p)); o=1; for(int i=0;i<E;i++){ int x,y,cost; scanf("%d%d%d",&x,&y,&cost); add_edge(x,y,cost); } for(int i=0;i<Q;i++){ int x,y; scanf("%d%d",&x,&y); add_edge(x,y); } lca(1); for(int i=1;i<o;i+=2){ printf("%d & %d -> %d\n",que[i].to,que[i+1].to,LCA[(i+1)/2]); } } return 0; } /* 8 7 5 1 2 2 2 3 4 2 4 5 4 5 6 1 6 7 6 7 4 7 8 4 3 4 3 5 5 6 6 7 1 8 */