hihocoder 1067 新近公共祖先·二 并查集+stl

hihocoder 1067 最近公共祖先·二 并查集+stl

题目链接：

hihocoder1067

题解思路：

面对10^5个 名字和10^5条询问,肯定要用到特殊的方法：

1.把所有的询问先存下来,然后再遍历一次整棵树得到所有答案

2.遍历的过程中   查询含当前节点的 所有询问，然后找到询问中的另一个节点；查看另一个节点的状态。

     如果另一个节点未访问过，接下来处理；

     如果另一个节点正在被访问（子节点未访问完）,则答案就是这个节点

     如果另一个节点已被访问过，则答案是它的正在被访问的根节点

3. 第二点的状态需要并查集处理

      未遍历时所有节点标记为未访问

      开始遍历,该节点标记为自己的下标

      遍历完后和它的父节点合并

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#define MAXN 100050
using namespace std;
map<string,int>id;         //保存名字的标号
vector<int>edge[MAXN];     //邻接表
vector<int>query[MAXN];    //保存含某个名字的所有问题的标号
string  name[MAXN];        //保存名字
string q1[MAXN],q2[MAXN];  //保存每个问题的左右两个名字
int ans[MAXN];
int fa[MAXN];
int name_s=1;


int get_id(string str)
{
    if(!id[str])
    {
        id[str]=name_s;
        name[name_s++]=str;
    }
    return id[str];
}


int Find(int x)
{
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}

void dfs(int loc,int pre)            //前序遍历
{
    fa[loc]=loc;
    for(int i=0;i<edge[loc].size();i++)
        dfs(edge[loc][i],loc);
    for(int i=0;i<query[loc].size();i++)                    //含这个节点(名字)的所有问题
    {
        int j=query[loc][i];
        int tmp=loc==id[q1[j]]? id[q2[j]] : id[q1[j]];      //找当前问题的另一个名字
        if(fa[tmp]==-1)                                     //另一个名字没访问过
            continue;
        ans[j]=Find(tmp);                                   
    }
    fa[loc]=Find(fa[pre]);                                  //合并到当前节点的根节点
    return;
}

int main()
{
    int n;
    string a,b;
    int t1,t2;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        t1=get_id(a);
        t2=get_id(b);
        edge[t1].push_back(t2);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>q1[i]>>q2[i];
        query[id[ q1[i] ] ].push_back(i);
        query[id[ q2[i] ] ].push_back(i);
    }
    memset(fa,-1,sizeof(fa));
    fa[0]=0;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        cout<<name[ans[i]]<<endl;
    return 0;
}