天天看點
傳回

LCA 最近公共祖先問題描述搜尋(暴力解)樸素算法倍增算法Tarjan 算法

Lowest Common Ancestors

  • 問題描述
  • 搜尋(暴力解)
  • 樸素算法
  • 倍增算法
  • Tarjan 算法

flyhite - minami

美波美波，沒有你我可怎麼活啊

問題描述

對于有根樹 T 的兩個結點 u、v，最近公共祖先 LCA(T, u, v) 表示一個結點x，滿足 x 是 u 和 v 的祖先且 x 離根盡可能的遠。在這裡，一個節點也可以是它自己的祖先。

資料格式參考 [洛谷 P3379]

搜尋(暴力解) 

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {

    public static void main(String[] args) {
    	Tree tree = new Tree(N);
    	tree.setRoot(S);
        tree.link(x, y);
        tree.LCA(u, v);
    }

    public class Tree {

        int N, root;
        List<Integer>[] V;
        boolean[] marked;

        Tree(int v) {
            this.V = new List[N = v];
            marked = new boolean[N];
            while (v-- > 0)
                V[v] = new ArrayList(3);
        }

        public void setRoot(int v) {
            marked[root] = false;
            marked[root = v] = true;
        }

        public void link(int v, int w) {
            V[v].add(w);
            V[w].add(v);
        }

        public int LCA(int u, int v) {
            return dfs(root, u, v) - 2;
        }

        private int dfs(int root, int u, int v) {
            int ans = root == u || root == v ? 1 : 0;
            for (int w : V[root]) {
                if (marked[w]) continue;
                marked[w] = true;
                ans += dfs(w, u, v);
                marked[w] = false;
                if (ans == 2) return ans + root;
                if (ans >  2) return ans;
            }
            return ans;
        }
    }
}

太暴力了，期望的複雜度不談

樸素算法

其實還是暴力

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    public void run() {
        Tree tree = new Tree(N);
        tree.link(x, y);
    	tree.setRoot(S);
        tree.LCA(u, v);
    }

    public class Tree {

        int N, root, time;
        int[] stamp;
        List<Integer>[] V;

        Tree(int v) {
            this.V = new List[N = v];
            stamp = new int[N];
            while (v-- > 0)
                V[v] = new ArrayList(3);
        }

        public void setRoot(int v) {
            Arrays.fill(stamp, -1);
            time = 0;
            dfs(root = v);
        }

        private void dfs(int root) {
            stamp[root] = time++;
            for (int w : V[root])
                if (stamp[w] == -1)
                    dfs(w);
        }

        public void link(int v, int w) {
            V[v].add(w);
            V[w].add(v);
        }

        public int LCA(int u, int v) {
            if (stamp[u] == stamp[v]) return u;
            if (stamp[u] > stamp[v]) return LCA(findFather(u), v);
            return LCA(u, findFather(v));
        }

        private int findFather(int v) {
            if (v == root) return root;
            int f = 0, ft = stamp[v];
            for (int w : V[v])
                if (stamp[w] < ft) {
                    ft = stamp[w];
                    f = w;
                }
            return f;
        }
    }
}

先預處理出 dfs序，然後根據dfs序 把 u、v 往最近公共祖先逆推

處理節點深度也是一樣的，先咋寫就咋寫，比較這還是屬于暴力方法的範疇，不推薦使用

最壞情況就是樹退化成連結清單，期望就是取随機樹高

期望時間複雜度 <O(n)，O(logn)>

期望空間複雜度 <O(n)，O(1)>

倍增算法 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    public void run() {
        Tree tree = new Tree(N);
        tree.link(x, y);
    	tree.setRoot(S);
        tree.LCA(u, v);
    }

    public class Tree {

        int N;
        int[][] ST;
        int[] depth;
        List<Integer>[] V;

        Tree(int v) {
            this.V = new List[N = v];
            ST = new int[N][log2(N) + 1];
            depth = new int[N];
            while (v-- > 0)
                V[v] = new ArrayList(3);
        }

        public void setRoot(int v) {
            Arrays.fill(depth, 0);
            for (int w : V[v])
                dfs(w, v);
        }

        private void dfs(int now, int fa) {
            depth[now] = depth[fa] + 1;
            ST[now][0] = fa;
            for (int i = 1; 1 << i <= depth[now]; i++)
                ST[now][i] = ST[ST[now][i - 1]][i - 1];
            for (int v : V[now])
                if (v != fa) dfs(v, now);
        }

        public void link(int v, int w) {
            V[v].add(w);
            V[w].add(v);
        }

        public int LCA(int u, int v) {
            if (depth[u] < depth[v]) return LCA(v, u);
            while (depth[u] > depth[v])
                u = ST[u][log2(depth[u] - depth[v])];
            if (u == v) return u;
            for (int k = log2(depth[u]); k >= 0; k--) {
                if (ST[u][k] != ST[v][k]) {
                    u = ST[u][k];
                    v = ST[v][k];
                }
            }
            return ST[u][0];
        }

        private int log2(int a) { return (int)(Math.log(a) / Math.log(2)); }
    }
}

用 O(nlogn) 的處理時間換來了穩定的 O(logn) 的查詢時間複雜度

算得上值當

Tarjan 算法

Tarjan算法是一種離線算法，它僅需一遍 dfs，在回溯過程中完成 LCA 的查找操作

多的我也不懂，闆子就完事了

值得注意的是在 Tarjan算法 裡每個節點隻會被通路一次，是以 并查集 find() 方法均攤複雜度在O(1)。

對于整個初始化過程，能在 O(n + m) 的複雜度下完成

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    public void run() {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt(), M = in.nextInt(), S = in.nextInt();
        Tree.Edge[] list = new Tree.Edge[M];
        Tree tree = new Tree(N);
        while (N-- > 1)
            tree.link(in.nextInt(), in.nextInt());
        for (int i = 0; i < M; i++)
            list[i] = tree. new Edge(in.nextInt(), in.nextInt(), i);
        for (int ans : tree.getLCAList(S, list))
            out.println(ans);
        out.flush();
    }

    public class Tree {

        int N;
        int[] parent;
        List<Integer>[] V;
        boolean[] marked;
        List<Edge>[] query;

        Tree(int v) {
            this.V = new List[N = ++v];
            this.query = new List[N];
            marked = new boolean[N];
            parent = new int[N];
            while (v-- > 0) {
                V[v] = new ArrayList(3);
                query[v] = new ArrayList(1);
            }
        }

        public class Edge {

            int u, v, queryIndex;

            Edge() { super(); }

            Edge(int u, int v) { this(u, v, 0); }

            Edge(int u, int v, int queryIndex) {
                this.u = u;
                this.v = v;
                this.queryIndex = queryIndex;
            }

            int other(int u) { return u == this.u ? v : this.u; }
        }

        public int[] getLCAList(int root, Edge[] queryList) {
            int[] LCAList = new int[queryList.length];
            for (int i = 0; i < N; i++) {
                marked[i] = false;
                query[i].clear();
            }
            for (Edge e : queryList) {
                query[e.u].add(e);
                query[e.v].add(e);
            }
            tarjan(root, LCAList);
            return LCAList;
        }

        private void tarjan(int v, int[] LCAList) {
            parent[v] = v;
            marked[v] = true;
            for (int w : V[v]) {
                if (marked[w]) continue;
                tarjan(w, LCAList);
                parent[w] = v;
            }
            for (Edge e : query[v])
                if (marked[e.other(v)])
                    LCAList[e.queryIndex] = find(e.other(v));
        }

        private int find(int v) { return v == parent[v] ? v : (parent[v] = find(parent[v])); }

        public void link(int v, int w) {
            V[v].add(w);
            V[w].add(v);
        }
    }

    static class InputReader {

        BufferedReader read;
        StringTokenizer tok;
        String delimiters;

        InputReader(InputStream in) { this(in, " \n\t\r\f"); }

        InputReader(InputStream in, String delimiters) {
            this.read = new BufferedReader(new InputStreamReader(in));
            this.delimiters = delimiters;
        }

        String next() {
            while (tok == null || !tok.hasMoreTokens())
                try {
                    tok = new StringTokenizer(read.readLine(), delimiters);
                } catch (IOException e) {
                    e.fillInStackTrace();
                }
            return tok.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
    }
}

寫完才發現，面向對象了，但沒完全面向對象

是以run方法就不用僞代碼了

算法随筆 java 算法 稀疏表 LCA
上一篇: 最近公共祖先問題（LCA）
下一篇: 最近公共祖先（LCA）

繼續閱讀