Tag Archives: LCA

LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉树和两个节点p,q,问p和q的最近公共祖先节点是哪个。LCA问题
思路:要找p和q的最近公共祖先,很直观的方法是找到从根节点分别到p和q的路径,然后把其中一条路径(比如根到p)上的点hash成path1,从另一条路径(比如根到q)的底端(q)往根节点走,把走过的每个点去path1中找,如果找到,则就是他们的LCA,因为这是距离q最近、且在path1中的点。
但是怎样找到根到p和q的路径呢。这里换一种思路,定义如下新的数据结构,par表示该节点的父节点,根节点的父节点为-1。

struct MyNode {
	TreeNode* node;
	int par;
	MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};

先整体把树层次遍历一遍,成为一个保存MyNode的数组,记录每个点的父节点在数组中的下标。在遍历的同时,记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。
找到路径之后,对其中一条路径hash,另一条路径在该hash中找。代码如下:

class Solution {
private:
	struct MyNode {
		TreeNode* node;
		int par;
		MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
	};
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<MyNode> nodes;
		int i = 0, j = 0;
		queue<MyNode> tree;
		tree.push({ root,-1 });
		while (!tree.empty()) {
			MyNode cur = tree.front();
			tree.pop();
			if (cur.node == NULL) continue;
			if (cur.node == p)i = nodes.size();
			if (cur.node == q)j = nodes.size();
			tree.push({ cur.node->left,nodes.size() });
			tree.push({ cur.node->right,nodes.size() });
			nodes.push_back(cur);
		}
		if (i == j)return nodes[i].node;
		unordered_set<int> path1;
		while (i != -1) {
			path1.insert(i);
			i = nodes[i].par;
		}
		while (j != -1) {
			if (path1.find(j) != path1.end()) {
				return nodes[j].node;
			}
			j = nodes[j].par;
		}
		return NULL;
	}
};

本代码提交AC,用时19MS。
讨论区还有一种递归的解法,很有意思。我们在以root为根的树中找p和q的LCA,如果root等于p或q其中之一,说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA,如果发现在左右子树中找到的LCA都不为null,说明他们p和q分别位于root的两个子树,类似样例中的5和1,则root就是他们的LCA。如果某个子树返回的LCA为空,说明p和q都不在这个子树中,则先遇到谁,谁就是LCA,比如样例中的5和4,都不在3的右子树,在递归3的左子树的时候,先遇到了5,所以5是LCA。
完整代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || root == p || root == q)return root;
		TreeNode* left = lowestCommonAncestor(root->left, p, q);
		TreeNode* right = lowestCommonAncestor(root->right, p, q);
		if (left != NULL&&right != NULL)return root;
		return left != NULL ? left : right;
	}
};

本代码提交AC,用时23MS。

LeetCode Lowest Common Ancestor of a Binary Search Tree

LeetCode Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉搜索树和两个节点,问这两个节点的最近公共祖先(LCA)。LCA问题很久以前在hihoCoder上做过好多,用到一些比较高级的算法。
这个题的一个特点是二叉树是二叉搜索树,二叉搜索树的特点是左孩子小于等于根节点,根节点小于等于右孩子。不失一般性,令p<=q,所以如果p<=root<=q,则p,q分立root两边,则root就是p,q的LCA。如果p,q都小于root,则递归在root->left找。如果p,q都大于root,则递归在root->right找。
递归的算法很容易就实现了,代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (p->val > q->val)swap(p, q);
		if (p->val <= root->val&&q->val >= root->val)return root;
		if (p->val < root->val&&q->val < root->val)return lowestCommonAncestor(root->left, p, q);
		if (p->val > root->val&&q->val>root->val)return lowestCommonAncestor(root->right, p, q);
	}
};

本代码提交AC,用时32MS。

hihoCoder 1069-最近公共祖先·三

hihoCoder 1069-最近公共祖先·三
#1069 : 最近公共祖先·三
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上上回说到,小Hi和小Ho使用了Tarjan算法来优化了他们的“最近公共祖先”网站,但是很快这样一个离线算法就出现了问题:如果只有一个人提出了询问,那么小Hi和小Ho很难决定到底是针对这个询问就直接进行计算还是等待一定数量的询问一起计算。毕竟无论是一个询问还是很多个询问,使用离线算法都是只需要做一次深度优先搜索就可以了的。
那么问题就来了,如果每次计算都只针对一个询问进行的话,那么这样的算法事实上还不如使用最开始的朴素算法呢!但是如果每次要等上很多人一起的话,因为说不准什么时候才能够凑够人——所以事实上有可能要等上很久很久才能够进行一次计算,实际上也是很慢的!
“那到底要怎么办呢?在等到10分钟,或者凑够一定数量的人两个条件满足一个时就进行运算?”小Ho想出了一个折衷的办法。
“哪有这么麻烦!别忘了和离线算法相对应的可是有一个叫做在线算法的东西呢!”小Hi笑道。
小Ho面临的问题还是和之前一样:假设现在小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁?
提示:最近公共祖先无非就是两点连通路径上高度最小的点嘛!
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,且每个输入文件中第一个出现的名字所确定的人是其他所有人的公共祖先。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。
样例输入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin
样例输出
Sam
Adam
Adam


这应该是最近公共祖先的最后一种算法了吧,hihoCoder还真是循序渐进啊,昨天刚刚学了RMQ-ST算法hihoCoder Problem 1068: RMQ-ST 算法,今天就用上了。
本题的解题思路也是非常的赞,首先把族谱树结构展开成一个数组B,当询问a,b节点的最近公共祖先时,在B中找到a,b最后出现的位置(也就是离开a,b节点的时候)an,bn,在区间[an,bn]上利用RMQ-ST算法求解区间深度最小的节点c,则c即为a,b的最近公共祖先,下面来具体讲解。
将族谱树展开成一个数组
为了利用RMQ-ST算法,需要将树形结构展开成一个数组,展开的方式是深度优先遍历树,将访问的节点顺序记录下来,不管是进入这个节点还是离开这个节点,都需要记录下来。比如下面一棵树:

是样例输入构成的一个家谱树,我们常规DFS这个树的序列是这样的:ASJMK。但是本题在进入和离开某个节点时都需要记录下来,而且每访问完一个子节点,要访问下一个子节点时,也需要记录当前父节点。比如访问完J准备访问M时,需要记录S,由此形成的序列为:ASJSMSAKA。
DFS生成的数组B长度大概为边数的两倍,所以复杂度级别只是O(n)的。
DFS之后就把树转换为了数组B[],因为使用RMQ-ST算法需要求某个区间的最小深度节点,所以在DFS的时候还需要记录每个节点的深度信息,而且还要记录每个节点最后访问的下标,这两点都不难,大家直接看代码即可。
RMQ-ST算法
得到数组B后就好办了,可以利用昨天学习的RMQ-ST算法求解2的幂区间长度间深度最小的节点,不过因为我们这题最终输出的是节点的名字而不是节点的深度,所以RMQ-ST比较的是深度,但存储的是节点名。
观察RMQ-ST算法的二重循环知道其复杂度为O(nlgn)。
在线求解
一切准备就绪后就可以求解了,首先根据字符串名字找到对应数字序号,然后查看两节点最后出现在树中的下标l,r,再讲[l,r]区间分成能覆盖[l,r]的2的幂的长度的半区间[l,t]和[t+1,r],最后求这两个区间最小深度的节点,输出其名称。
完整代码如下:

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int n,m,k;//k全部记录将树转换成数组tree[]是的下标,转换结束时k即为tree[]的长度
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
int tree[2*MAX_N];//DFS将树转换为的数组
int depth[MAX_N];//每个点在树中的深度
int rmq[MAX_N][30];//区间深度最低值
int last_show[MAX_N];//某个元素最后出现在tree中的位置(下标)
//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}
//深度遍历树
void DFS(int root,int deep)
{
     tree[k++]=root;//进入即记录
     depth[root]=deep;//记录深度
     int sons=f_s[root].size();
     for(int i=0;i<sons;i++)
     {
          DFS(f_s[root][i],deep+1);
          tree[k++]=root;//每返回一次都要记录一次根节点
     }
     last_show[root]=k-1;//root节点最后出现的位置
}
//求a,b最小值
inline int get_min(int a,int b)
{
     return a<b?a:b;
}
void init_rmq()
{
     for(int j=0;j<k;j++)
          //rmq[j][0]=depth[tree[j]];
          rmq[j][0]=tree[j];//保存的是这个节点,而不是它的深度,方便最后输出
     int q=floor(log((double)k)/log(2.0));
     for(int i=1;i<=q;i++)
     {
          for(int j=k-1;j>=0;j--)
          {
               rmq[j][i]=rmq[j][i-1];
               if(j+(1<<(i-1))<k)
               {
                    if(depth[rmq[j+(1<<(i-1))][i-1]]<depth[rmq[j][i]])//+优先级高于<<,所以改j+1<<(i-1)为j+(1<<(i-1))
                         rmq[j][i]=rmq[j+(1<<(i-1))][i-1];
               }
                    //rmq[j][i]=get_min(rmq[j][i],rmq[j+1<<(i-1)][i-1]);
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     cin>>n;
     string name1,name2;
     int index1,index2;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
     }
     k=0;//开始时树的下标为0,DFS完之后正好是tree[]数组的长度,可以作为rmq-st的n
     DFS(0,0);
     init_rmq();
     cin>>m;
     int l,r,t;
     while(m--)
     {
          cin>>name1>>name2;
          if(name1==name2)
          {
               cout<<name1<<endl;
               continue;
          }
          index1=store_name(name1);
          index2=store_name(name2);
          l=last_show[index1];
          r=last_show[index2];
          if(l>r)//保证l<=r
          {
               int tmp=r;
               r=l;
               l=tmp;
          }
          t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
          cout<<index_name[get_min(rmq[l][t],rmq[r-(1<<t)+1][t])]<<endl;//r-(1<<t)+1,记得+1
     }
     return 0;
}

本代码提交AC,用时202MS,内存8MB。
相比于hihoCoder Problem 1067: 最近公共祖先·二,本题的的DFS+RMQ-ST算法是在线算法,也就是每来一个询问可以立即回答,而且复杂度为O(nlgn)还不错。
至此,hihoCoder的最近公共祖先问题完整结束,共使用三种算法,后两种算法都利用DFS,阅读时可以互相参照:最近公共祖先问题

POJ 1330-Nearest Common Ancestors

POJ 1330-Nearest Common Ancestors
Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19432 Accepted: 10292
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
Source
Taejon 2002


昨天被hihoCoder Problem 1067: 最近公共祖先·二的离线算法虐了之后,今天在POJ上找了一个水题来重塑信心,这个题也是最近公共祖先问题,只不过它是目前为止最简单的,和hihoCoder Problem 1062: 最近公共祖先·一类似,甚至更简单,因为这个题每个case只询问一次,所以没必要用离线算法,而且给的就是数字,不是字符串,连转换都不要。直接记录一个节点node1的所有祖先,然后从下往上查找另一个节点node2的所有祖先,每找到一个祖先,则判断这个祖先是否是node1的祖先,如果是,则这就是他们的公共祖先。
这一次我甚至连set和map都没有用,因为给定的是连续的整数,直接用数组当hash即可,而且查找效率比set和map还快。
完整代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);
     int t,n;
     int node1,node2;
     cin>>t;
     while(t--)
     {
          cin>>n;
          vector<int> s_f(n+1,0);//s_f[i]为第i个节点的父亲,开始时所有节点的父亲为0
          for(int i=0;i<n-1;i++)
          {
               cin>>node1>>node2;
               s_f[node2]=node1;//保存输入关系
          }
          cin>>node1>>node2;
          vector<int> node1_father(n+1,0);//node1的父亲
          node1_father[node1]=1;//自己是自己的祖先
          while(s_f[node1]!=0)
          {
               node1_father[s_f[node1]]=1;//记录哪些点是node1的父亲
               node1=s_f[node1];
          }
          if(node1_father[node2]!=0)//node2也是自己的祖先
          {
               cout<<node2<<endl;
               continue;
          }
          while(s_f[node2]!=0)
          {
               if(node1_father[s_f[node2]]!=0)//从下网上找node2的祖先是否出现在node1的祖先里
               {
                    cout<<s_f[node2]<<endl;
                    break;
               }
               else
                    node2=s_f[node2];
          }
     }
     return 0;
}

本代码提交AC,用时125MS,内存336K。
关于最近公共祖先问题,还有一种牛逼的在线算法RMQ,在hihoCoder上也有提到,下回再战!

hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二
#1067 : 最近公共祖先·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上上回说到,小Hi和小Ho用非常拙劣——或者说粗糙的手段山寨出了一个神奇的网站,这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁。远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息,并且搭建了一个小小的网站来应付来自四面八方的请求。
但正如我们所能想象到的……这样一个简单的算法并不能支撑住非常大的访问量,所以摆在小Hi和小Ho面前的无非两种选择:
其一是购买更为昂贵的服务器,通过提高计算机性能的方式来满足需求——但小Hi和小Ho并没有那么多的钱;其二则是改进他们的算法,通过提高计算机性能的利用率来满足需求——这个主意似乎听起来更加靠谱。
于是为了他们第一个在线产品的顺利运作,小Hi决定对小Ho进行紧急训练——好好的修改一番他们的算法。
而为了更好的向小Ho讲述这个问题,小Hi将这个问题抽象成了这个样子:假设现小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁?
提示一:老老实实分情况讨论就不会出错的啦!
提示二:并查集其实长得很像一棵树你们不觉得么?
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,第一个出现的名字所确定的人是其他所有人的公共祖先。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。
样例输入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin
样例输出
Sam
Adam
Adam


hihoCoder确实是个练习算法的好网站,之前我们写过朴素的最近公共祖先问题:hihoCoder Problem 1062: 最近公共祖先·一,但那是一个效率比较低的方法,这一次,hihoCoder详细给我们介绍了最近公共祖先的离线算法,而且讲解非常详细。
网站上的讲解详细,易于理解,我这里简单概括一下。所谓离线算法就是先把询问搜集起来,如果某个询问能先回答,则记录答案,直到把所有询问都解答了;与之相对的是在线算法,也就是每提出一个询问,我都要实时的马上回答。
离线算法综合了DFS和并查集。给定一个族谱(树形结构),我们先把每一个节点染成白色,并且在初始并查集中,每个点都是一个独立的集合,然后从树根开始深度优先遍历,当第一次经过某个节点a的时候,把它由白色改为灰色;如果第二次访问该节点的时候(也就是离开该点的时候),则把它由灰色改为黑色。
当a每次由白变灰之后,查看询问中是否出现过该节点,如果出现了,则查看询问中另一个节点b的颜色,如果b是灰色,则<a,b>的最近公共祖先就是b,因为b是灰色的,所以访问a之前肯定访问了b,所以它们的最近公共祖先是b;如果b是黑色,此时已经离开b了,并不能直接说明a和b的关系,但是<a,b>的最近公共祖先肯定在灰色链上,所以我们只要找出b向上的第一个灰色节点,就是<a,b>的最近公共祖先;如果b是白色,则说明b还没有访问,没有关于b的信息,所以我们暂时不管这个询问,等到访问到b时,a肯定不是白色,这是可以依据前两条规则得出它们的最近公共祖先。
当a每次由灰变黑之后,我们需要在并查集中将a和a的直接父节点合并UNION,因为当a由灰变黑时,a及其子树都访问结束了,但是a的直接父节点还没有访问结束,也就是说a的直接父节点还是灰色的,这样我们就记录了a向上的第一个灰色节点,这为上面的第二种情况判断做准备。
最近公共祖先的离线算法概括起来就是上面的内容,简单易懂也很强大。但是因为算法既包含DFS,又包含并查集,对初学者来说有一定的难度,而且这个题给出的数据是字符串形式的,数据量又很大,有很多细节需要注意。
我先把完整的代码贴出来,然后讲一下主要过程。

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int color[MAX_N]={0};//0:白;1:灰;2:黑,初始颜色都是白色
int s_f[MAX_N];//son_father。s_f[i]表示第i个儿子的直接父亲
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
vector<vector<int> > show_at(MAX_N);//show_at[i]表示第i个人在哪些询问里出现过
int q_l[MAX_N];//第i个询问的左边
int q_r[MAX_N];//第i个询问的右边
int father[MAX_N];//用于并查集,和s_f不一样
vector<string> ans;//最终结果
//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          father[curr_index]=curr_index;//初始的时候,并查集中每个元素都是一个独立的集合
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}
//并查集FIND操作
int find_father(int name)
{
     return name==father[name]?name:(father[name]=find_father(father[name]));
}
//并查集UNION操作
void union_father(int name1,int name2)
{
     father[find_father(name1)]=find_father(name2);
}
//深度遍历族谱树
void DFS(int root)
{
     color[root]=1;//首先修改颜色为灰色
     int show_time=show_at[root].size();//查看该元素是否在询问里出现
     if(show_time!=0)
     {
          for(int i=0;i<show_time;i++)//判断所有询问
          {
               int column=show_at[root][i];
               int left=q_l[column];//找到该询问的左右元素
               int right=q_r[column];
               if(left==right)//如果是左右相同,则该自身即是其最近公共祖先
                    ans[column]=index_name[left];
               else
               {
                    if(left==root)//判断当前访问的是左边的还是右边的
                    {
                         if(color[right]==1)//另一个点为灰色
                              ans[column]=index_name[right];//结果即为该灰色点
                         else if(color[right]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(right)];//找其向上最近的灰色节点
                    }
                    else
                    {
                         if(color[left]==1)//另一个点为灰色
                              ans[column]=index_name[left];
                         else if(color[left]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(left)];
                    }
               }
          }
     }
     int sons=f_s[root].size();//查看是否有孩子节点
     if(sons!=0)
     {
          for(int i=0;i<sons;i++)
               DFS(f_s[root][i]);//深度遍历其所有孩子
     }
     color[root]=2;//改颜色为黑色
     union_father(root,s_f[root]);//和直接父节点UNION
}
int main()
{
     ios_base::sync_with_stdio(false);//取消同步,加速
     cin.tie(0);
     //freopen("input.txt","r",stdin);
     int n,m;
     string name1,name2;
     int index1,index2;
     cin>>n;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
          s_f[index2]=index1;
     }
     cin>>m;
     ans.resize(m);
     for(int i=0;i<m;i++)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          q_l[i]=index1;
          q_r[i]=index2;
          show_at[index1].push_back(i);
          show_at[index2].push_back(i);
     }
     DFS(0);
     for(int i=0;i<m;i++)
          cout<<ans[i]<<endl;
     return 0;
}

摆在我们面前的第一个问题就是数据的输入问题,题目给的每个人名都是字符串,当然我们可以直接用字符串构建一个树结构,然后进行查找、比较、赋值等操作,但是这样的时空效率都比较低,所以我们可以先用map<string,int> name_index和vector<string> index_name来记录人名字符串和人名数字下标,这样我们在DFS+并查集的时候可以只使用数字下标,到最后输出的时候再转换为字符串,提高效率。记录并返回人名数字下标的操作在函数int store_name(string name);中。
我们还需要记录父子关系,因为一个父亲可以有多个孩子,所以父亲-孩子关系需要用二维数组vector<vector<int> > f_s(MAX_N);来表示;而一个孩子只可能有一个父亲,所以孩子-父亲关系可以用一维数组int s_f[MAX_N];来表示。
还有两个数组需要初始化,每个节点的颜色初始化为白色,在并查集中每个节点单独为一个集合。
然后就是存储询问了。正如前面对LCA离线算法的描述,每当一个节点从白色变为灰色时,我们都要查看询问中是否出现过该节点。输入的询问中有很多节点,怎样来快速判断所有询问中是否有某个节点以及该询问中的另一个节点呢?如果这个问题处理不好,很可能就是TLE,反正我前两个版本都是因为这个原因TLE的。
这个问题可以通过两个步骤来解决,都是用空间来换时间。因为每一个询问都是由左右两个人名组成的,那么我们先把每次询问的左右两个人名记录在int q_l[MAX_N];和int q_r[MAX_N];中。然后还用一个二维数组vector<vector<int> > show_at(MAX_N);来记录某一个节点在哪些询问里出现过。这样当我们DFS到某个节点a时,首先查看show_at[a]这个数组是否为空,如果为空,说明a没有出现在任何一次询问中;如果不为空,则show_at[a]记录了a出现的所有询问的序号,根据这个序号,我们再去查q_l和q_r,这样就可以取出a出现时的那个询问的左右两个人名是什么了。所以整个过程只需要O(1)的时间,大大提高了时间效率。
因为题目中说明了

第一个出现的名字所确定的人是其他所有人的公共祖先。

所以我们以第一个人名下标0来DFS树结构。DFS的过程和上面的算法描述一致,我这里就不多说了,代码中都有详细的注释。
还有一个小问题需要注意,因为编译器不一样,在用vector声明二维数组的时候,我在VS2010下可以这样:

vector<vector<int>> a; //sth

但是提交之后会报Compile Error的错误:error: ‘>>’ should be ‘> >’ within a nested template argument list,也就是说这个编译器把>>看成了移位操作符,所以我们在两个箭头之间加一个空格> >这样就没问题了。
我上面的代码版本提交后AC,用时711MS,内存30MB。这是我迄今为止内存消耗最大的一次AC。
总的来说,这个题是好题,很考验选手的综合能力,特别是本题用到的各种数据结构较多,需要全盘考虑,不断优化。

hihoCoder 1062-最近公共祖先·一

hihoCoder 1062-最近公共祖先·一
#1062 : 最近公共祖先·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho最近发现了一个神奇的网站!虽然还不够像58同城那样神奇,但这个网站仍然让小Ho乐在其中,但这是为什么呢?
“为什么呢?”小Hi如是问道,在他的观察中小Ho已经沉迷这个网站一周之久了,甚至连他心爱的树玩具都弃置一边。
“嘿嘿,小Hi,你快过来看!”小Ho招呼道。
“你看,在这个对话框里输入我的名字,在另一个对话框里,输入你的名字,再点这个查询按钮,就可以查出来……什么!我们居然有同一个祖祖祖祖祖爷爷?”
“诶,真是诶……这个网站有点厉害啊。”小Hi不由感叹道。
“是啊,这是什么算法啊,这么厉害!”小Ho也附和道。
“别2,我说的是他能弄到这些数据很厉害,而人类的繁殖树这种层数比较浅的树对这类算法的要求可是简单的不得了,你都能写出来呢!”小Hi道。
“啊?我也能写出来?可是……该从哪开始呢?”小Ho困惑了。
小Ho要面临的问题是这样的,假设现在他知道了N个人的信息——他们的父亲是谁,他需要对于小Hi的每一次提问——两个人的名字,告诉小Hi这两个人的是否存在同一个祖先,如果存在,那么他们的所有共同祖先中辈分最低的一个是谁?
提示:不着急,慢慢来,另外我有一个问题:挖掘机技术哪家强?!
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^2,M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人)。
输出
对于每组测试数据,对于每个小Hi的询问,输出一行,表示查询的结果:如果根据已知信息,可以判定询问中的两个人存在共同的祖先,则输出他们的所有共同祖先中辈分最低的一个人的名字,否则输出-1。
样例输入
11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu
样例输出
JiaDaishan
JiaZheng
-1


最近公共祖先问题:给定一个家谱图,问某两个人的最近的公共祖先是谁,如果没有公共祖先,输出-1。最简单的方法题目提示得很清楚了:

当然你也先将一个人的祖先全都标记出来,然后顺着另一个的父亲一直向上找,直到找到第一个被标记过的结点,便是它们的最近公共祖先结点了。

所以我就简单粗暴的使用STL的MAP和SET来解决问题了。假设需要判断的两个人名分别为son1和son2,那么①首先把*son1*及其所有祖先都找到并加入到一个set中,然后②首先判断son2在不在前面的set中,③如果不在,再依次判断son2的祖先在不在set中。
这里需要注意几点:
1. son1的祖先包括son1本身,比如第二个样例中的JiaBaoyu和JiaZheng,JiaZheng的祖先就包括JiaZheng自己,所以需要上面的第①和②步。
2. 为什么使用set而不是vector呢?因为②③步需要在son1的祖先中搜索,set内部用红黑树实现,搜索的效率高于vector。
知道了以上几点,就可以很快的写出代码了,完整代码如下:

#include<iostream>
#include<map>
#include<string>
#include <set>
using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);
     int n,t;
     cin>>n;
     string son,father;
     map<string,string> son_father;//map[son]=father
     for(int i=0;i<n;i++)
     {
          cin>>father>>son;
          son_father.insert(make_pair(son,father));
     }
     cin>>t;
     string son1,son2,comm_father;
     while(t--)
     {
          comm_father="";
          cin>>son1>>son2;
          //vector<string> grand_fathers;
          set<string> grand_fathers;//使用set的查找效率高于vector
          grand_fathers.insert(son1);//注意,son1,son2本身也是一个祖先,一定要加进去,否则错!
          while(son_father.find(son1)!=son_father.end())
          {
               grand_fathers.insert(son_father[son1]);
               son1=son_father[son1];
          }
          if(grand_fathers.find(son2)!=grand_fathers.end())//首先son2本身也是一个祖先,所以先判断一下//使用set的查找效率高于vector
          {
               if(t!=0)
                    cout<<son2<<endl;
               else
                    cout<<son2;
               continue;
          }
          while(son_father.find(son2)!=son_father.end())
          {
               if(grand_fathers.find(son_father[son2])!=grand_fathers.end())
               {
                    comm_father=son_father[son2];//因为是son2从下往上找,所以第一个出下的肯定是最近的公共祖先
                    break;
               }
               else
                    son2=son_father[son2];
          }
          if(t!=0)
          {
               if(comm_father=="")
                    cout<<"-1"<<endl;
               else
                    cout<<comm_father<<endl;
          }
          else
          {
               if(comm_father=="")
                    cout<<"-1";
               else
                    cout<<comm_father;
          }
     }
     return 0;
}

本代码提交AC,用时4MS,内存0MB。
之前说了,我这种解法是非常简单粗暴的,事实上最近公共祖先问题是一个经典问题,有很多经典算法可以解决,我后面会进一步研究。