POJ-1330 Nearest Common Ancestors

2016年08月20日 |

acm

| acm

• 题目：
• 解析&吐槽：

题目：

 Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 25094 Accepted: 13049

Description
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.

Input
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.

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

Sample Input

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

Sample Output

4
3

解析&吐槽：

求最近公共祖先的算法。本来应该用转化为 RMQ || tarjan 算法的方法来做的，可惜我不会_(:зゝ∠)_

这里用了两种方法来做，第一种是用 dfs 遍历。设两个要找的节点分别为 first 和 second，那么 如果有一个节点的子节点中同时包含有 first 和 second，则此节点是它们的一个公共祖先（但不一定 是最近的），我们可以利用 dfs 的后序遍历的方法，从下往上处理。dfs 函数返回一个 bool 值， 如果此节点包含 first 或者 second 的子节点或者就是这两个节点之一，将会返回 true；不包含 first 和 second 的时候返回 false。依次遍历每一个节点的孩子节点，如果有两个 dfs 返回 true， 代表此节点就是我们要找的节点。我通过抛出异常的方式退出了递归链，这只是为了方便而已，工程中 可不建议这么写。需要注意的是，dfs 的开头如果发现当前的节点就是 first 或者 second 之一， 不能立刻返回 true，必须要递增计数器，否则如果 first 是 second 的祖先的话，就处理不了了。

贴上代码：

#include <iostream>
//#include <cstdio>
#include <cstring>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <list>
#include <iterator>
#include <cmath>
#include <queue>

using namespace std;

int ans, first, second;
vector<int> child[10010];
int pre[10010];

bool dfs(int root)
{
    int res = 0;
    if (root == first || root == second)
        ++res;

    for (int i = 0;i < child[root].size();++i)
    {
        if (dfs(child[root][i]))
            ++res;
        if (res >= 2)
        {
            ans = root;
            throw int();
        }
    }

    if (res == 1)
        return true;
    else
        return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1;i <= n;++i)
        {
            child[i].clear();
            pre[i] = i;
        }
        int m = n - 1;
        while(m--)
        {
            int a, b;
            cin >> a >> b;
            child[a].push_back(b);
            pre[b] = a;
        }

        cin >> first >> second;
        ans = 0;

        int root = 1;
        while (pre[root] != root)
            root = pre[root];

        try { dfs(root); }
        catch (int) {}

        cout << ans << endl;
    }
}

耗时 266ms。

第二种方法简单粗暴，使用保存父节点的方式存储树，然后从 first 节点向上回溯到 root，标记所有遇到 的节点。然后从 second 向上回溯，找到的第一个被标记的节点就是 LCA。

// oj.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
//#include <cstdio>
#include <cstring>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <list>
#include <iterator>
#include <cmath>
#include <queue>

using namespace std;

int pre[10010];
bool visited[10010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1;i <= n;++i)
        {
            visited[i] = false;
            pre[i] = i;
        }
        int m = n - 1;
        while (m--)
        {
            int a, b;
            cin >> a >> b;
            pre[b] = a;
        }

        int first, second;

        cin >> first >> second;

        visited[first] = true;
        while (pre[first] != first)
        {
            first = pre[first];
            visited[first] = true;
        }

        while (pre[second] != second && !visited[second])
            second = pre[second];

        cout << second << endl;
    }
}

耗时 125ms。顺带一提，这道题如果把 cin 改成 scanf，时间可以减少到 16ms。