[Algorithm] Rescue the Princess

알고리즘 해결 과정을 도식화 한 그림도 추가할 예정입니다!

package Recursive_Tree_Graph;

import java.io.*;
import java.util.*;

// Virtual Judge(ZOJ) - Rescue the Princess
public class RescueThePrincess_VirtualJudge_ZOJ {

    static final int LOG = 7;
    static int n;
    static int m;
    static int q;
    static Graph graph;
    static Data data;
    static int[] arr;

    static int cnt;
    static Graph graphs;
    static LcaData lcaData;

    // 공주님을 구하고 돕는 메서드를 구현합니다
    static void SaveAndHelpPrincess(FastReader fr, StringBuilder sb) throws Exception {

        // 문제에서 주어진 입력값
        n = fr.nextInt();
        m = fr.nextInt();
        q = fr.nextInt();

        initGraph();

        for (int i = 0; i < m; i++) {
            int value = fr.nextInt();
            int VALUE = fr.nextInt();
            graph.Edge(value, VALUE);
            graph.Edge(VALUE, value);
        }

        findMethod();
        build();
        buildMethod();
        buildLca();

        for (int i = 0; i < q; i++) {
            // 문제에서 주어진 입력값
            int u = fr.nextInt();
            int v = fr.nextInt();
            int w = fr.nextInt();

            int arr_value = arr[u];
            int array_Value = arr[v];
            int Array_VALUE = arr[w];

            if (lcaData.root[arr_value] != lcaData.root[array_Value]
                    || lcaData.root[arr_value] != lcaData.root[Array_VALUE]) {
                sb.append("No\n");
                continue;
            }

            if (check(arr_value, array_Value, Array_VALUE)) {
                sb.append("Yes\n");
            } else {
                sb.append("No\n");
            }
        }
    }

    static final class FastReader {
        private final BufferedReader br;
        private final char[] buffer = new char[1 << 73];
        private int index = 0;
        private int len = 0;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in), 1 << 73);
        }

        private int read() throws IOException {
            if (index >= len) {
                len = br.read(buffer, 0, buffer.length);
                index = 0;
                if (len <= 0) return -1;
            }
            return buffer[index++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int val = 1;
            if (c == '-') {
                val = -1;
                c = read();
            }

            int value = 0;
            while (c > ' ') {
                value = value * 10 + (c - '0');
                c = read();
            }
            return value * val;
        }
    }

    static final class Graph {
        int[] arr;
        int[] Array;
        int[] Arr;
        int edgeIndex;
        int nodeCount;
        int edgeCount;

        Graph(int nodeCount, int edgeCount) {
            this.nodeCount = nodeCount;
            this.edgeCount = edgeCount;
            arr = new int[nodeCount + 1];
            Arrays.fill(arr, -1);
            Array = new int[Math.max(edgeCount, 1)];
            Arr = new int[Math.max(edgeCount, 1)];
            edgeIndex = 0;

        }

        void Edge(int node, int value) {
            Array[edgeIndex] = value;
            Arr[edgeIndex] = arr[node];
            arr[node] = edgeIndex++;
        }
    }

    static final class Data {
        int[] arr;
        int[] Array;
        int[] edges;
        int[] iterEdge;
        boolean[] check;
        int cnt;

        Data(int n, int m) {
            arr = new int[n + 1];
            Array = new int[n + 1];
            edges = new int[n + 1];
            iterEdge = new int[n + 1];
            Arrays.fill(edges, -1);
            check = new boolean[m];
            cnt = 0;
        }
    }

    static final class LcaData {
        int[][] arr;
        int[] depth;
        int[] root;

        LcaData(int size) {
            arr = new int[LOG][size + 1];
            depth = new int[size + 1];
            root = new int[size + 1];
        }
    }

    static void initGraph() {
        graph = new Graph(n, 7 * m);
    }

    static void findMethod() {
        data = new Data(n, m);

        int[] stack = new int[n];
        int val = 0;

        for (int i = 1; i <= n; i++) {
            if (data.arr[i] != 0) continue;

            stack[val++] = i;

            while (val > 0) {
                int value = stack[val - 1];

                if (data.arr[value] == 0) {
                    data.arr[value] = data.Array[value] = ++data.cnt;
                    data.iterEdge[value] = graph.arr[value];
                }

                int e = data.iterEdge[value];

                if (e != -1) {
                    data.iterEdge[value] = graph.Arr[e];

                    if (data.edges[value] != -1 && e == (data.edges[value] ^ 1)) {
                        continue;
                    }

                    int node = graph.Array[e];

                    if (data.arr[node] == 0) {
                        data.edges[node] = e;
                        stack[val++] = node;
                    } else {
                        data.Array[value] = Math.min(data.Array[value], data.arr[node]);
                    }
                } else {
                    val--;

                    int edge = data.edges[value];
                    if (edge != -1) {
                        int Edge = graph.Array[edge ^ 1];
                        data.Array[Edge] = Math.min(data.Array[Edge], data.Array[value]);

                        if (data.Array[value] > data.arr[Edge]) {
                            data.check[edge >> 1] = true;
                        }
                    }
                }
            }
        }
    }

    static void build() {
        arr = new int[n + 1];
        cnt = 0;

        int[] stack = new int[n];

        for (int i = 1; i <= n; i++) {
            if (arr[i] != 0) continue;

            cnt++;
            int val = 0;
            stack[val++] = i;
            arr[i] = cnt;

            while (val > 0) {
                int value = stack[--val];

                for (int e = graph.arr[value]; e != -1; e = graph.Arr[e]) {
                    int edgeId = e >> 1;
                    if (data.check[edgeId]) continue;

                    int node = graph.Array[e];
                    if (arr[node] == 0) {
                        arr[node] = cnt;
                        stack[val++] = node;
                    }
                }
            }
        }
    }

    static void buildMethod() {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (data.check[i]) cnt++;
        }

        graphs = new Graph(cnt, 7 * cnt);

        for (int value = 1; value <= n; value++) {
            for (int e = graph.arr[value]; e != -1; e = graph.Arr[e]) {
                if ((e & 1) == 1) continue;

                int node = graph.Array[e];
                int val = arr[value];
                int arr_value = arr[node];

                if (val != arr_value) {
                    graphs.Edge(val, arr_value);
                    graphs.Edge(arr_value, val);
                }
            }
        }
    }

    static void buildLca() {
        lcaData = new LcaData(cnt);

        int[] stack = new int[cnt];
        int[] arr = new int[cnt + 1];

        for (int i = 1; i <= cnt; i++) {
            if (lcaData.root[i] != 0) continue;

            int val = 0;
            stack[val++] = i;
            lcaData.root[i] = i;
            lcaData.depth[i] = 0;
            lcaData.arr[0][i] = 0;
            arr[i] = 0;

            while (val > 0) {
                int value = stack[--val];

                for (int e = graphs.arr[value]; e != -1; e = graphs.Arr[e]) {
                    int node = graphs.Array[e];
                    arr[node] = value;
                    lcaData.root[node] = i;
                    lcaData.depth[node] = lcaData.depth[value] + 1;
                    lcaData.arr[0][node] = value;
                    stack[val++] = node;

                    if (node == arr[value]) continue;
                    if (lcaData.root[node] != 0) continue;

                }
            }
        }

        for (int num = 1; num < LOG; num++) {
            for (int value = 1; value <= cnt; value++) {
                int mid = lcaData.arr[num - 1][value];
                lcaData.arr[num][value] = (mid == 0 ? 0 : lcaData.arr[num - 1][mid]);
            }
        }
    }

    static int lca(int a, int b) {
        if (lcaData.depth[a] < lcaData.depth[b]) { // 생성형 AI를 사용한 lca 구현
            int integer = b;
            b = a;
            a = integer;
        }

        int d = lcaData.depth[a] - lcaData.depth[b];
        for (int num = 0; num < LOG; num++) {
            if (((d >> num) & 1) != 0) {
                a = lcaData.arr[num][a];
            }
        }

        if (a == b) return a;

        for (int num = LOG - 1; num >= 0; num--) {
            if (lcaData.arr[num][a] != lcaData.arr[num][b]) {
                a = lcaData.arr[num][a];
                b = lcaData.arr[num][b];
            }
        }

        return lcaData.arr[0][a];
    }

    static int dist(int a, int b) {
        int c = lca(a, b);
        return lcaData.depth[a] + lcaData.depth[b] - 2 * lcaData.depth[c]; // 생성형 AI 값 사용
    }

    static boolean check(int data, int a, int b) {
        return dist(a, b) == dist(a, data) + dist(data, b);
    }

    public static void main(String[] args) throws Exception {
        FastReader fr = new FastReader();
        StringBuilder sb = new StringBuilder();

        int t = fr.nextInt();
        while (t-- > 0) {
            // 공주님을 구하고 돕는 메서드를 실행합니다
            SaveAndHelpPrincess(fr, sb);
        }

        System.out.print(sb.toString());
    }
}