[转载] 关于LCA和RMQ问题及其互相转化

PHP学习笔记之日期、时间函数

学习RMQ的sparse table算法

Aug 1

felix021 @ 2008-8-1 19:52 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(9218) | Via 本站原创

大 | 中 | 小

from http://hi.baidu.com/trooper/blog/item/ad377fd9ee6d072d10df9bc2.html

p.s. Felix终于看懂了, 建议先看看RMQ的实现算法之sparse table

一、最近公共祖先(Least Common Ancestors)

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

这里给出一个LCA的例子：

例一

对于T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}

则有：

LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3

二、RMQ问题(Range Minimum Query)

RMQ问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小值下标。这时一个RMQ问题的例子：

例二

对数列：5,8,1,3,6,4,9,5,7 有：

RMQ(2,4)=3
RMQ(6,9)=6

RMQ问题与LCA问题的关系紧密，可以相互转换，相应的求解算法也有异曲同工之妙。

下面给出LCA问题向RMQ问题的转化方法。

对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的值存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做R[i]。如果结点E[i]的深度记做D[i]，易见，这时求LCA(T,u,v)，就等价于求 E[RMQ(D,R[u],R[v])]，(R[u]<R[v])。例如，对于第一节的例一，求解步骤如下：

数列E[i]为：1,2,1,3,4,3,5,3,1
R[i]为：1,2,4,5,7
D[i]为：0,1,0,1,2,1,2,1,0

于是有：

LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1
LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3
LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3

易知，转化后得到的数列长度为树的结点数的两倍加一，所以转化后的RMQ问题与LCA问题的规模同次
Reference : ZOJ 1141

Write a program that takes as input a rooted tree and a list of pairs of vertices. For each pair (u,v) the program determines the closest common ancestor of u and v in the tree. The closest common ancestor of two nodes u and v is the node w that is an ancestor of both u and v and has the greatest depth in the tree. A node can be its own ancestor (for example in Figure 1 the ancestors of node 2 are 2 and 5)

The data set starts with the tree description, in the form:

nr_of_vertices
vertex:(nr_of_successors) successor1 successor2 ... successorn
......

where vertices are represented as integers from 1 to n. The tree description is followed by a list of pairs of vertices, in the form:

nr_of_pairs
(u v) (x y) ...

The input contents several data sets (at least one).

Note that white-spaces (tabs, spaces and line breaks) can be used freely in the input.

For each common ancestor the program prints the ancestor and the number of pair for which it is an ancestor. The results are printed on the standard output on separate lines, in to the ascending order of the vertices, in the format: ancestor:times

For example, for the following tree:

the program input and output is:

Input

5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5) (1,4) (4,2)
(2,3)
(1,3) (4,3)

Output

2:1
5:5

代码如下：

//这个算法是说在已知的d[i][j]表示从i开始到i+2^j的最小数
//然后由d[i][j]和d[i+2^j][j]推出d[i][j+1]
//这就是所谓的分割区间的算法，时间复杂度为O(nlogn).和那个线段树差不多，两者并没有多大的差别

#include <iostream.h>
#include <string.h>

#define MAX 905

int R[MAX], L[2 * MAX], E[2 * MAX], num[MAX], d[2 * MAX][12], count[MAX];
int *link[MAX], tot;
bool v[MAX];

//数列E[i]为：1,2,1,3,4,3,5,3,1

//R[i]为：1,2,4,5,7

//L[i]为：0,1,0,1,2,1,2,1,0

//E存放深度搜索时访问的节点的标号
//R存放各个节点的访问的时间
//L访问节点的深度
int DFS(int x, int d)
{
  int i;
  if (!v[x]) {
    v[x] = 1;
    R[x] = tot;
  }
  L[tot] = d;
  E[tot++] = x;
  for (i = 0; i < num[x]; i++) {
    DFS(link[x][i], d + 1);
    L[tot] = d;
    E[tot++] = x;
  }
  return 0;
}

int RMQ(int v1, int v2)
{
  int k = 0;
  while ((1 << (k + 1)) < (v2 - v1 + 1))
    k++;
  if (L[d[v1][k]] < L[d[v2 - (1 << k) + 1][k]])
    return E[d[v1][k]];
  else
    return E[d[v2 - (1 << k) + 1][k]];
}

int LCA(int v1, int v2)
{
  if (R[v1] < R[v2])
    return RMQ(R[v1], R[v2]);
  else
    return RMQ(R[v2], R[v1]);
}

int main()
{
  int n, i, j, v1, v2, m;
  char c;
  bool root[MAX];
  while (cin >> n) {
    memset(root, 0, sizeof(root));
    for (i = 0; i < n; i++) {
      cin >> v1;
      cin >> c;
      while (c != ':')
        cin >> c;
      cin >> c;
      while (c != '(')
        cin >> c;
      cin >> num[v1 - 1];
      link[v1 - 1] = new int[num[v1 - 1]];
      cin >> c;
      while (c != ')')
        cin >> c;
      for (j = 0; j < num[v1 - 1]; j++) {
        cin >> v2;
        root[v2 - 1] = 1;
        link[v1 - 1][j] = v2 - 1;
      }
    }
    for (i = 0; i < n; i++)
      if (!root[i])
        break;
    memset(v, 0, sizeof(v));
    tot = 0;
    DFS(i, 0);
    for (i = 0; i < n; i++)
      delete[]link[i];
    for (j = 0; (1 << j) <= tot; j++)
      for (i = 0; i + (1 << j) <= tot; i++) {
        if (j == 0)
          d[i][j] = i;
        else {
          if (L[d[i][j - 1]] <
              L[d[i + (1 << (j - 1))][j - 1]])
            d[i][j] = d[i][j - 1];
          else
            d[i][j] =
                d[i + (1 << (j - 1))][j -
                    1];

        }
      }
    cin >> m;
    memset(count, 0, sizeof(count));
    for (i = 0; i < m; i++) {
      cin >> c;
      while (c != '(')
        cin >> c;
      cin >> v1 >> c >> v2;
      v1--;
      v2--;
      count[LCA(v1, v2)]++;
      cin >> c;
      while (c != ')')
        cin >> c;
    }
    for (i = 0; i < n; i++)
      if (count[i])
        cout << i + 1 << ':' << count[i] << endl;
  }
  return 0;
}

Program @ TrackBack : http://post.blog.hexun.com/bloodybat/trackback.aspx?articleid=2832372&key=632785863675270000

欢迎扫码关注：