1.倍增法
import java.io.*;
import java.util.*;
public class Main{
static class Reader{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer=new StringTokenizer("");
String next() throws IOException {
while(!tokenizer.hasMoreTokens()) {
tokenizer=new StringTokenizer(br.readLine());
}
return tokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static int N=500010,M=2*N,n,m,s,idx;
static int[]h=new int[N];
static int[]e=new int[M];
static int[]ne=new int[M];
static int[]dep=new int[N];//dep[u]存储u节点的深度
static int[][]fa=new int[N][20];//f[u][i]存储从u节点向上跳 2^i 层的祖先节点 因为最多只有50万个节点所以高度最高为50万 2^20=100万 可以包含
static void add(int a,int b) {
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
static void dfs(int u,int father) {
dep[u]=dep[father]+1;
fa[u][0]=father;//向上跳一步就是它的父亲节点
for (int i = 1; i <=19; i++) {
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i!=-1;i=ne[i]) {
int j=e[i];
if(j!=father) dfs(j, u);
}
}
static int lca(int u,int v) {
if(dep[u]<dep[v]) {//要确保u的层数大于等于v 即u在v的下面 方便后面代码书写
int t=u;
u=v;
v=t;
}
//先跳到同一层
for (int i = 19; i >=0 ; i--)
if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return v;
//再跳到lca的下一层
for (int i = 19; i >=0 ; i--)
if(fa[u][i]!=fa[v][i]) {
u=fa[u][i];
v=fa[v][i];
}
//返回父节点
return fa[u][0];
}
public static void main(String[] args) throws IOException {
Arrays.fill(h, -1);
Reader sc=new Reader();
n=sc.nextInt();
m=sc.nextInt();
s=sc.nextInt();
for (int i = 0; i < n-1; i++) {
int a=sc.nextInt();
int b=sc.nextInt();
add(a, b);
add(b, a);
}
dfs(s,0);
for (int i = 0; i < m; i++) {
int u=sc.nextInt();
int v=sc.nextInt();
System.out.println(lca(u, v));
}
}
}
1.tarjan算法
-
tarjan算法Java实现主要在query具有困难
下面代码query[i]存储的是需要查询的两个点
import java.io.*;
import java.util.*;
public class Main3 {
static class Reader{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer=new StringTokenizer("");
String next() throws IOException {
while (!tokenizer.hasMoreTokens()){
tokenizer=new StringTokenizer(br.readLine());
}
return tokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static class el{
int u;
int v;
public el(int u, int v) {
this.u = u;
this.v = v;
}
}
static int N=500010,n,m,s,idx;
static int[]h=new int[N];
static int[]e=new int[N];
static int[]ne=new int[N];
static int[]p=new int[N];
static el[]query=new el[N];
static boolean[]st=new boolean[N];
static int[] ans=new int[N];
static void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
static int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
static void tarjan(int u,int fa){//即深搜
st[u]=true;//入u时标记u
for (int i=h[u];i!=-1;i=ne[i]){
int j = e[i];
if(j==fa) continue;
if(!st[j]){
tarjan(j,u);
p[j]=u;//回u时 j指向u
}
}
//离u时 枚举lca
for (int i = 0; i < m; i++) {
if(u==query[i].u){
if(st[query[i].v])ans[i]=find(query[i].v);
}
if(u==query[i].v){
if(st[query[i].u])ans[i]=find(query[i].u);
}
}
}
public static void main(String[] args) throws IOException {
Arrays.fill(h,-1);
for (int i = 0; i < N; i++) {
p[i]=i;
}
Reader sc=new Reader();
n=sc.nextInt();
m=sc.nextInt();
s=sc.nextInt();
for (int i = 0; i < n-1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a,b);
add(b,a);
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
query[i]=new el(u,v);
}
tarjan(s,-1);
for (int i = 0; i < m; i++) {
System.out.println(ans[i]);
}
}
}
下面代码query[u]存储的是 查询的另一个点和查询编号
import java.io.*;
import java.util.*;
public class Main {
static class Reader{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer=new StringTokenizer("");
String next() throws IOException {
while (!tokenizer.hasMoreTokens()){
tokenizer=new StringTokenizer(br.readLine());
}
return tokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static class el{
int v;
int i;
public el(int v, int i) {
this.v = v;
this.i = i;
}
}
static int N=500010,n,m,s,idx;
static int[]h=new int[N];
static int[]e=new int[N];
static int[]ne=new int[N];
static int[]p=new int[N];
//static el[]query=new el[N];
static ArrayList<ArrayList<el>>query=new ArrayList<>();
static boolean[]st=new boolean[N];
static int[] ans=new int[N];
static void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
static int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
static void tarjan(int u,int fa){//即深搜
st[u]=true;//入u时标记u
for (int i=h[u];i!=-1;i=ne[i]){
int j = e[i];
if(j==fa) continue;
if(!st[j]){
tarjan(j,u);
p[j]=u;//回u时 j指向u
}
}
//离u时 枚举lca
for(el e:query.get(u)){
int v=e.v;
int i=e.i;
if(st[v]) ans[i]=find(v);
}
}
public static void main(String[] args) throws IOException {
Arrays.fill(h,-1);
for (int i = 0; i < N; i++) {
p[i]=i;
query.add(new ArrayList<>());
}
Reader sc=new Reader();
n=sc.nextInt();
m=sc.nextInt();
s=sc.nextInt();
for (int i = 0; i < n-1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a,b);
add(b,a);
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
query.get(u).add(new el(v,i));
query.get(v).add(new el(u,i));
}
tarjan(s,-1);
for (int i = 0; i < m; i++) {
System.out.println(ans[i]);
}
}
}
