HiHo一下 Week15 最近公共祖先 离线算法 + STL::vector初探

HiHo

描述

上上回说到，小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

思路

这次相比上次的LCA（最近公共祖先）问题，数据量大了很多，因此不能再用之前的算法，这次引入离线算法Tarjan。
所谓离线算法指的是收集一定量查询后一起进行输出，也就是说查询的数量对算法运行时间不会有多大影响。打个不恰当的例子，吃一口饭拉一坨翔是不是很费时间还容易菊花疼得痔疮吧，吃两顿再拉一坨就节省时间多了。ヽ(́◕◞౪◟◕‵)ﾉ
Tarjan算法主要使用的是并查集+后序DFS。
简单的说，建好树后进行DFS后序遍历，将树上的节点分为两类，一类是已经遍历过的称为A类，一类是没有遍历的称为B，其外还有一个节点就是当前结点，很容易发现，当前结点和任意一个已经遍历过的节点的LCA都是同一个，只要在遍历到该节点时看一下包含该节点的查询，如果另外一个节点还没遍历，那么搁置，如果已经遍历过了，就说明，二者的最近公共祖先就是A类的LCA。每当遍历完一个节点，就将其置为遍历过，且将其集合并到父节点上。
我语文不好表达得不清楚，这个博客讲得还好。。。
ps:这里要讲一下C++里面stl vector的用法。vector是一个动态容量的顺序容器。需要引用头文件<vector>。
声明：template <class T> v。
示例：

vector<int> v; //声明 v
vector<int> u(10); //声明u并初始化空间为10
u[5] = 5; //因为之前初始化过空间过，所以可以直接访问u[5]
u.at(5) = 5; //这句和上面的功能相同，但是at函数会检查容量，如果爆了会报 out_of_range 错误
u.push_back(12); //这行代码在u的最后插上一个为12的值，这里虽然只有u[5]有赋值，但是由于之前初始化空间10了，所以会将12赋给第11个元素也就是u[10]
cout << u.size()<<"  "<<u.capacity(); // 会输出"11 20"，由于vector动态增长，每次不够用了会自动开辟10空间，所以capacity为20，但是最后一个存有数据的元素为第11个，所以size为11。
v.push_back(12); //v一直是空的，所以这里等价于v[0]=12
u.clear(); //清除
//删除指定位置元素 这里用到迭代器
vector<int>::iterator it;
it = u.begin();
u.erase(it); //这样就删除了u的第一个元素

代码

#include<iostream>
#include<string>
#include<map>
#include<vector> 
#define max 100005
using namespace std;
std::map<string,int> header;
std::vector<int> tree[max];
int index=0;
string name[max];
std::map<std::pair<int,int>,string> l;
int set[max];
int ancestor[max];
void buildTree(){
    int n;
    string a,b;
    std::map<string,int>::iterator idIta;
    std::map<string,int>::iterator idItb;
    cin >>n;
    while(n--){
        cin >> a;
        cin >> b;
        idIta = header.find(a);
        if(idIta == header.end()) {
            name[index] = a;
            header[a] = index++;
            idIta = header.find(a);
        }
        idItb = header.find(b);
        if(idItb == header.end()) {
            name[index] = b;
            header[b] = index++;
            idItb = header.find(b);
        }
        tree[idIta->second].push_back(idItb->second);
    }
}
struct point{
    int x;
    int y;
}temp;
std::vector<int> query[max];
std::vector<point> q;
void readQuery()
{
    int n;
    string a,b;
    cin >> n;
    std::map<string,int>::iterator idIta;
    std::map<string,int>::iterator idItb;
    for(int i=0;i<n;i++){
        cin >> a;
        cin >> b;
        idIta = header.find(a);
        idItb = header.find(b);
        query[idIta->second].push_back(idItb->second);
        query[idItb->second].push_back(idIta->second);
        if(idIta->second<idItb->second)
            {temp.x = idIta->second;temp.y = idItb->second;}            
        else {temp.x = idItb->second;temp.y = idIta->second;}
        q.push_back(temp);
    }
}
void initSet(){
    for (int i=0;i<index;i++)
        {
            set[i] = i;
            ancestor[i] = i;
        }
}
int findSet(int x){
    if(x != set[x]) set[x] = findSet(set[x]);
    return set[x]; 
}
void unionSet(int x,int y){
    int xF = findSet(x);
    int yF = findSet(y);
    if(xF == yF) return;
    else set[yF] = xF;
}
bool flag[max];
void DFS(int x){
    for (int i=0;i<tree[x].size();i++){
        DFS(tree[x][i]);
        unionSet(x,tree[x][i]);
        ancestor[findSet(x)] = x;
    }
    flag[x] = 1;
    for (int i=0;i<query[x].size();i++){
        if(flag[query[x][i]]){
            string t = name[ancestor[findSet(query[x][i])]];
            if(x<query[x][i]){
                l[pair<int,int>(x,query[x][i])] = t;
            }else{
                l[pair<int,int>(query[x][i],x)] = t;
            }
        }
    }
}
void output(){
    for(int i=0;i<q.size();i++){
        std::map<pair<int,int>,string>::iterator itt;
        itt = l.find(pair<int,int>(q[i].x,q[i].y));
        cout <<itt->second<<endl;
    }
}
int main(){
    buildTree();
    //memset(flag, 0, sizeof(flag));
    initSet();
    readQuery();
    DFS(0);
    output();
    return 0;
}