首页 > 专题系列 > Java解POJ > POJ 1330 Nearest Common Ancestors [解题报告] Java
2013
11-09

POJ 1330 Nearest Common Ancestors [解题报告] Java

Nearest Common Ancestors

问题描述 :

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:



In the figure, each node is labeled with an integer from {1, 2,…,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

输入:

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

输出:

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

样例输入:

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

样例输出:

4
3

解题代码:

import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
    int MAX = 10001;
    Vector< Integer> tree[] = new Vector[MAX + 1];; // �����
    byte[] flag = new byte[MAX]; // �ュ害���锛��浜���炬����
    int parent[] = new int[MAX];;
    int rank[] = new int[MAX];;
    int ancestor[] = new int[MAX];
    int visited[] = new int[MAX];
    StringBuilder sb = new StringBuilder();
    byte ret;
    {
        for (int i = 1; i < MAX; i++)
            tree[i] = new Vector< Integer>();
    }

    public static void main(String[] args) {
        Main poj = new Main();
        java.util.Scanner s = new java.util.Scanner(System.in);
        int test = s.nextInt();
        int i = 0;
        while (++i <= test) {
            int length = s.nextInt();
            poj.initial(length);
            int a;
            int b;
            for (int j = 1; j < length; j++) {
                a = s.nextInt();
                b = s.nextInt();
                poj.flag[b] = -1;
                poj.tree[a].add(b);
            }
            int root;
            for (root = 1; root <= length; root++)
                if (poj.flag[root] != -1)
                    break;
            a = s.nextInt();
            b = s.nextInt();
            poj.LCA(root, a, b);
        }
        System.out.print(poj.sb.toString());
    }

    void initial(int n) {
        ret = 1;

        for (int i = 1; i <= n; i++) {
            flag[i] = 0;
            parent[i] = i;
            rank[i] = 0;
            ancestor[i] = 0;
            visited[i] = 0;
            tree[i].clear();

        }
    }

    int find(int x) {
        if (x == parent[x])
            return x;
        else
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if (a == b)
            return;
        if (rank[a] < rank[b])
            parent[a] = b;
        else if (rank[a] > rank[b])
            parent[b] = a;
        else {
            parent[a] = b;
            rank[b]++;
        }
    }

    void LCA(int u, int x, int y) {
        ancestor[u] = u;
        for (int i = 0; i < tree[u].size(); i++) {
            LCA(tree[u].get(i), x, y);
            if (ret == 0)
                return;
            union(u, tree[u].get(i));
            ancestor[find(u)] = u;
        }
        visited[u] = 1;

        if (u == x && visited[y] == 1 && ret == 1) {

            sb.append(ancestor[find(y)]);
            sb.append('\n');
            ret = 0;
            return;
        }
        if (u == y && visited[x] == 1 && ret == 1) {
            {

                sb.append(ancestor[find(x)]);
                sb.append('\n');
                ret = 0;
                return;
            }
        }
    }
}

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks