tarjan算法求LCA问题解析 + 模板 洛谷P3379——JAVA版

题目链接：传送门：洛谷P3379

关于算法解决LCA的问题我在网上找了很久，因为它是离线算法的关系，答案输出的顺序总是存在或多或少的问题，网上似乎也没有对着模板题敲这个算法AC的代码，特别是JAVA版本。

前缀知识：

1.并查集，2.dfs，3.邻接表。

算是几个基础的知识点了，很多算法都有引用到，不会的话还是先去学这些吧。

—————————————————————————————

LCA问题有两种解决思路：

在线算法：对每次的询问进行直接处理，并输出解。

离线算法：把所有的询问先存起来，最后再一步到位求出所有解，并输出。

属于离线算法，基于dfs和并查集实现。

算法思路：

如下图

我询问{7,5},{2,6},{1,9}的LCA是多少。

我首先需要存储这三组关系，很容易就能想到邻接表实现。

你可能有一刻会疑惑为什么不用桶实现，我存sz[7]=5,sz[5]=7;sz[2]=6,sz[6]=2;sz[9]=1,sz[1]=9不就表明关系了？

而且时间复杂度是O(1),空间复杂度也就O(n)。但请不要忘了，我同一个结点可能会被询问多次，这样一来就无法桶存储了。

我们从根节点1开始，我从左往右前序遍历整个树,并且标记已经走过的结点。

流程开始：

我现在在节点1，我发现，1号节点与9号节点是有一组关系的。那么我就要去询问，9号节点是否被访问过，显然没有，那我们先不管他，标记一号节点已经被访问，然后往下递，这里请不要着急，慢慢往下看。

我现在我访问到了2号节点，发现此节点与6号节点有关系，但是同样，6号节点并没有被访问过，所以我们继续往下递归

来到3号节点，他没有任何数字与他组成一组询问，所以也不用管他，我们继续走

现在我们来到了7号节点，已经不能往下走了，需要开始进行回溯。那么这个时候，我回溯到3号节点时，需要标记，3号节点是7号节点的祖先，这里我们用并查集来实现，走到8号节点也无法往下了，也用同样回溯，并回溯到3时同样标记8号节点的祖先为3号节点。

也就是说，在回溯时我们需要将当前回溯结点的根节点信息用并查集记录起来，你问我为什么？我们继续。

用这种走法我们走到节点5，这时候7，8号节点的祖先是3，而3号节点的祖先是2。但因为我们是用并查集模拟的，那么显然7，8号节点的真实祖先在查找之后理应也是2。

那么现在，关键点来了，我发现5号节点和7号节点存在一组询问，并且我发现，7号节点已经被访问过，那么我现在就能直接得到，7号节点的当前祖先2，便是{7,5}的最近公共祖先。

是不是感到很懵？什么？你忽然就告诉我你求出解了？我都还没反应过来！

没关系，看下解析吧。

你现在回溯走到了5号节点代表了什么？是不是代表2号节点的左节点当中，并不完全包含{7,5}两个节点。也就是说2号节点的左节点中，根本不存在{7,5}的LCA，但存在着7节点。那如果现在你不认2是公共祖先，难道要等2号节点再往上回溯到1再去认祖先吗？想想是不是这样。

稍微思考一下，其实马上就能想明白这个问题。

用这种方法我就可以递归到节点6，然后发现2已经访问过了，得到{2,6}的祖先是当前2并查集寻找到的祖先1。

再到9找到{1,9}的祖先是1，完成。

这样，我们竟然就只花了O(n+q)的复杂度就把多次询问全部解答完了，q次询问其实应该乘上并查集的查找时间，但并查集处理这种问题的情况下，查找时间会是一个很小的常数，并不需要我们去过多考虑，优秀！

算法解LCA带给我的最大问题是，因为是离线算法的缘故，对于每一次的询问，我都要按“顺序”去输出它，对于答案的存法我想了很多，网上似乎有C++版本用存储去解决的，无奈博主对C++并不精通，涉及到了要我老命，所以我用了一个字符串数组，将询问的数字升序，然后变成了字符串，当我找到了一个答案后，我会将一组查询升序后存入map，代码的最后for一遍去重新向map询问答案是多少。

听不懂没事，上题目和代码，附上注释！

题目链接：传送门：洛谷P3379

题目描述：

温馨提示：我的代码中使用了快读快出。

ini()这个方法就等于类的();

out.print()等于.out.print();

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;public class Main
{static int next[],end[],top[];static int nex[],en[],to[];static int sz[],o,v;static boolean book[];//两个经典邻接表构建static void con(int a,int b){next[++o]=top[a];top[a]=o;end[o]=b;}static void co(int a,int b){nex[++v]=to[a];to[a]=v;en[v]=b;}//经典并查集构建static void cha(int a,int b){a=find(a);b=find(b);if (a!=b){sz[b]=a;}}static int find(int x){if (sz[x]==x)return x;return sz[x]=find(sz[x]);}//tarjan算法static void dfs(int x){book[x]=true;//标记该点已经走过for (int i=top[x];i!=0;i=next[i]){if (!book[end[i]]){dfs(end[i]);//如果没走过，往下递归cha(x,end[i]);//递归完后回溯，合并结点}}for (int i=to[x];i!=0;i=nex[i])//遍历与该结点x所有有关系的结点{if (book[en[i]])//如果当前与x有关系的结点已经被询问过，那么答案存map里{if (en[i]<x)map.put(en[i]+" "+x, find(en[i]));//记得长相要升序哦else map.put(x+" "+en[i], find(en[i]));}}}static HashMap<String, Integer> map;public static void main(String[] args) throws IOException{int n=ini();int m=ini();int s=ini();map=new HashMap<>();//存答案的map//经典邻接表构建，用于存图next=new int [n<<1];end=new int [n<<1];top=new int [n+1];o=0;sz=new int [n+1];//并查集记录父节点的数组book=new boolean [n+1];//记录是节点是否已遍历sz[n]=n;for (int i=1;i<n;i++){sz[i]=i;int a=ini();int b=ini();con(a,b);con(b,a);}//又是一个经典邻接表数组，该数组存的是节点间是否有关系to=new int [n+1];nex=new int [m<<1+1];en=new int [m<<1+1];v=0;String ans[]=new String [m+1];//存答案长啥样子for (int i=1;i<=m;i++){int a=ini();int b=ini();if (a<b)ans[i]=a+" "+b;//答案升序存长相else ans[i]=b+" "+a;co(a,b);co(b,a);}dfs(s);//从根节点s开始遍历for (int i=1;i<=m;i++){out.println(map.get(ans[i]));//用询问的长相ans[i]去询问map给出解}out.flush();}/*
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5*/
//下面这些是快读和快出,与此算法无关，无需去细品static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static int ini() throws IOException{in.nextToken();return (int)in.nval;}static double ind() throws IOException{in.nextToken();return in.nval;}static String ins() throws IOException{in.nextToken();return in.sval;}static long inl() throws IOException{in.nextToken();return (long) in.nval;}}

最后如果有能力，可以想想此算法如何解决多次询问多点的公共祖先，如果依然像我这样升序，数组存询问的长相，嘿嘿嘿，存答案的时间复杂度就炸死你，想不出的建议学在线算法，就没这些苦恼了，不过一般题目似乎都是求两点，因为我网上根本找不到求多点的题目