tarjian求LCA

 1 //tarjian离线求LCA
 2 #include
 3 #define N 420000
 4 struct hehe{
 5     int next;
 6     int to;
 7     int lca;
 8 };
 9 hehe edge[N];//树的链表
10 hehe qedge[N];//需要查询LCA的两节点的链表
11 int n,m,p,x,y;
12 int num_edge,num_qedge,head[N],qhead[N];
13 int father[N];
14 int visit[N];//判断是否被找过
15 void add_edge(int from,int to){//建立树的链表
16     edge[++num_edge].next=head[from];
17     edge[num_edge].to=to;
18     head[from]=num_edge;
19 }
20 void add_qedge(int from,int to){//建立需要查询LCA的两节点的链表
21     qedge[++num_qedge].next=qhead[from];
22     qedge[num_qedge].to=to;
23     qhead[from]=num_qedge;
24 }
25 int find(int z){//找爹函数
26     if(father[z]!=z)
27         father[z]=find(father[z]);
28     return father[z];
29 }
30 int dfs(int x){//把整棵树的一部分看作以节点x为根节点的小树
31     father[x]=x;//由于节点x被看作是根节点，所以把x的father设为它自己
32     visit[x]=1;//标记为已被搜索过
33     for(int k=head[x];k;k=edge[k].next)//遍历所有与x相连的节点
34         if(!visit[edge[k].to]){//若未被搜索
35             dfs(edge[k].to);//以该节点为根节点搞小树
36             father[edge[k].to]=x;//把x的孩子节点的father重新设为x
37         }
38     for(int k=qhead[x];k;k=qedge[k].next)//搜索包含节点x的所有询问
39         if(visit[qedge[k].to]){//如果另一节点已被搜索过
40             qedge[k].lca=find(qedge[k].to);//把另一节点的祖先设为这两个节点的最近公共祖先
41             if(k%2)//由于将每一组查询变为两组，所以2n-1和2n的结果是一样的
42                 qedge[k+1].lca=qedge[k].lca;
43             else
44                 qedge[k-1].lca=qedge[k].lca;
45         }
46 }
47 int main(){
48     scanf("%d%d%d",&n,&m,&p);//输入节点数，查询数和根节点
49     for(int i=1;ii){
50         scanf("%d%d",&x,&y);//输入每条边
51         add_edge(x,y);
52         add_edge(y,x);
53     }
54     for(int i=1;i<=m;++i){
55         scanf("%d%d",&x,&y);//输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录
56         add_qedge(x,y);
57         add_qedge(y,x);
58     }
59     dfs(p);//进入以p为根节点的树的深搜
60     for(int i=1;i<=m;i++)
61         printf("%d ",qedge[i*2].lca);//两者结果一样，只输出一组即可
62     return 0;
63 }