Tarjan：
pre：
1、$dfn[x]$ 为时间戳，表示访问这个节点时已经 dfs 了 $dfn[x]-1$ 个节点，它为第 $dfn[x]$ 个被访问的节点。
2、$low[x]$ 为一个最小值，表示这个节点隶属于哪一个强连通分量（每一个 low 值都是以第一个被访问的在这个强连通分量中的节点时间戳为下标）（单独一个节点也为强连通分量）
3、$sta[x]$ 为一个栈，它内部的东西是以 dfs 序顺序压入的节点，它首先在叶节点弹栈，再在父节点弹栈，保证强连通分量判断时的不重不漏。
4、$cir[x]$ 表示 x 这个节点隶属于哪个强连通分量。
5、$len[x]$ 表示 x 这个强连通分量的大小。
实战：
tarjan 算法可以处理重边与自环。
LCA:
1 #include<cstdio>
2 #define N 420000
3 struct hehe{
4 int next;
5 int to;
6 int lca;
7 };
8 hehe edge[N];//树的链表
9 hehe qedge[N];//需要查询LCA的两节点的链表
10 int n,m,p,x,y;
11 int num_edge,num_qedge,head[N],qhead[N];
12 int father[N];
13 int visit[N];//判断是否被找过
14 void add_edge(int from,int to){//建立树的链表
15 edge[++num_edge].next=head[from];
16 edge[num_edge].to=to;
17 head[from]=num_edge;
18 }
19 void add_qedge(int from,int to){//建立需要查询LCA的两节点的链表
20 qedge[++num_qedge].next=qhead[from];
21 qedge[num_qedge].to=to;
22 qhead[from]=num_qedge;
23 }
24 int find(int z){//找爹函数
25 if(father[z]!=z)
26 father[z]=find(father[z]);
27 return father[z];
28 }
29 int dfs(int x){//把整棵树的一部分看作以节点x为根节点的小树
30 father[x]=x;//由于节点x被看作是根节点，所以把x的father设为它自己
31 visit[x]=1;//标记为已被搜索过
32 for(int k=head[x];k;k=edge[k].next)//遍历所有与x相连的节点
33 if(!visit[edge[k].to]){//若未被搜索
34 dfs(edge[k].to);//以该节点为根节点搞小树
35 father[edge[k].to]=x;//把x的孩子节点的father重新设为x
36 }
37 for(int k=qhead[x];k;k=qedge[k].next)//搜索包含节点x的所有询问
38 if(visit[qedge[k].to]){//如果另一节点已被搜索过
39 qedge[k].lca=find(qedge[k].to);//把另一节点的祖先设为这两个节点的最近公共祖先
40 if(k%2)//由于将每一组查询变为两组，所以2n-1和2n的结果是一样的
41 qedge[k+1].lca=qedge[k].lca;
42 else
43 qedge[k-1].lca=qedge[k].lca;
44 }
45 }
46 int main(){
47 scanf("%d%d%d",&n,&m,&p);//输入节点数，查询数和根节点
48 for(int i=1;i<n;++i){
49 scanf("%d%d",&x,&y);//输入每条边
50 add_edge(x,y);
51 add_edge(y,x);
52 }
53 for(int i=1;i<=m;++i){
54 scanf("%d%d",&x,&y);//输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录
55 add_qedge(x,y);
56 add_qedge(y,x);
57 }
58 dfs(p);//进入以p为根节点的树的深搜
59 for(int i=1;i<=m;i++)
60 printf("%d ",qedge[i*2].lca);//两者结果一样，只输出一组即可
61 return 0;
62 }
无向图：
1、缩点 + 判断 dcc（点双连通分量） + 割点 + 建树
首先，tarjan 大框架没问题，有几句代码需要解释一下。
1、$low[to]>=dfn[x]$ ：判断割点的条件（重要）。
Code：
1 inline void tarjan(int x,int opt=0){
2 dfn[x]=low[x]=++tar; sta[++up]=x;
3 for(register int i=first[x],tmp;i;i=a[i].next){
4 int to=a[i].to;
5 if(!dfn[to]){
6 tarjan(to);
7 low[x]=min(low[x],low[to]);
8 if(low[to]>=dfn[x]){
9 opt++; sum++;
10 if(x!=1||opt>1) cut[x]=1;
11 do{
12 tmp=sta[up--];
13 cir[tmp]=sum;
14 dcc[sum].push_back(tmp);
15 }while(tmp!=to);
16 cir[x]=sum;
17 dcc[sum].push_back(x);
18 }
19 }
20 else low[x]=min(low[x],dfn[to]);
21 }
22 }
23 signed main(){
24 tarjan(1);
25 for(register int i=1;i<=n;++i) if(cut[i]) cir[i]=id[i]=++cnt;
26 for(register int i=1;i<=sum;++i)
27 for(register int j=0;j<dcc[i].size();++j){
28 int to=dcc[i][j];
29 if(cut[to]) addtr(i,id[to]);
30 }
31 }
2、割边（仅限无向图）
1、$dfn[x]<low[to]$ ：割边判定条件。若满足 $dfn[x]<low[to]$ ，就是说在以 to 为根的子树中，若不经过 x--to 这条边，都无法到达 x 及 时间戳小于 x 的节点。去掉这条边就好像是隔绝了这两个图，所以割边的判定条件得证。
Code：
1 inline void tarjan(int x,int opt){
2 dfn[x]=low[x]=++tar;
3 for(register int i=first[x];i;i=a[i].next){
4 int to=a[i].to;
5 if(!dfn[to]){
6 tarjan(to,i);
7 low[x]=min(low[x],low[to]);
8 if(low[to]>dfn[x]) br[i]=br[i^1]=1;
9 }
10 else if(i!=(opt^1)) low[x]=min(low[x],dfn[to]);
11 }
12 }
13 inline void dfs(int x){
14 in[x]=dcc;
15 for(register int i=first[x];i;i=a[i].next){
16 int to=a[i].to;
17 if(in[to]||br[i]) continue;
18 dfs(to);
19 }
20 }
有向图：
1、缩点
Code：
1 dfn[x]=low[x]=++tar;
2 sta[++up]=x; judge[x]=1;
3 for(register int i=first[x];i;i=a[i].next){
4 int to=a[i].to;
5 if(!dfn[to]){
6 tarjan(to);
7 low[x]=min(low[x],low[to]);
8 }
9 else if(judge[to]) low[x]=min(low[x],dfn[to]);
10 }
11 if(dfn[x]==low[x]){
12 ++circle;
13 do{
14 tmp=sta[up--]; judge[tmp]=0;
15 cir[tmp]=circle;
16 }while(tmp!=x);
17 }