最近公共祖先问题
时间限制: 1 Sec 内存限制: 128 MB
题目描述
已知一个无向图和若干个节点，且该无向图是连通无环图。
请以节点1作为根节点，输出任意两节点的最近公共祖先(Least Common Ancestor)
子树的个数可以有任意多个，不一定是二叉树
输入
图的节点数m和边n,询问数q
边的信息：每一条边(1,2)表示节点1连接到节点2(n行)
询问信息：1 2，询问节点1和节点2的LCA(q行)
输出
节点的LCA
样例输入
12 11 4
1 2
2 5
6 5
1 4
1 3
7 3
3 8
8 9
8 10
9 11
10 121 9
2 6
9 7
12 4
样例输出
1
2
3
1
import java.util.Scanner;public class Main {static int n, e, q;static boolean edges[][];static boolean marked[];static String res = "";static int way[][];static int step = 0;static int flag = 0;static int sign[];public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();e = in.nextInt();q = in.nextInt();edges = new boolean[n + 1][n + 1];marked = new boolean[n + 1];way = new int[n + 1][n + 1];sign = new int[n + 1];for (int i = 0; i < e; i++) {int x = in.nextInt();int y = in.nextInt();edges[x][y] = true;edges[y][x] = true;}for (int i = 0; i < q; i++) {int x = in.nextInt();int y = in.nextInt();if (way[x][0] != 1) {dfs(1, x);reset();}// System.out.println("x=" + x + Arrays.toString(way[x]));if (way[y][0] != 1) {dfs(1, y);reset();}//System.out.println("y=" + y + Arrays.toString(way[y]));outer:for(int j=n;j>=0;j--) {if(way[x][j]==0)continue;for(int k=n;k>=0;k--) {if(way[x][j]==way[y][k]) {System.out.println(way[x][j]);break outer;}}}}in.close();}//深度优先搜索private static void dfs(int x, int y) {if (flag == 1) {return;}//System.out.println("x="+x+" step="+step);marked[x] = true;way[y][step] = x;if (x == y) {flag = 1;return;}for (int i = 1; i <= n; i++) {if (edges[x][i] == true && marked[i] == false) {sign[x] = 1;step++;dfs(i, y);}if (i == n && sign[x] == 0) {way[y][step] = 0;step--;if (step >= 1) {sign[way[y][step]] = 0;}}}}private static void reset() {step = 0;flag = 0;for (int j = 0; j <= n; j++) {marked[j] = false;sign[j] = 0;}}
}