首页 > ACM题库 > HDU-杭电 > HDU 4547-CD操作-DFS-[解题报告]HOJ
2015
07-25

HDU 4547-CD操作-DFS-[解题报告]HOJ

CD操作

问题描述 :

  在Windows下我们可以通过cmd运行DOS的部分功能,其中CD是一条很有意思的命令,通过CD操作,我们可以改变当前目录。
  这里我们简化一下问题,假设只有一个根目录,CD操作也只有两种方式:
  
  1. CD 当前目录名\…\目标目录名 (中间可以包含若干目录,保证目标目录通过绝对路径可达)
  2. CD .. (返回当前目录的上级目录)
  
  现在给出当前目录和一个目标目录,请问最少需要几次CD操作才能将当前目录变成目标目录?

输入:

输入数据第一行包含一个整数T(T<=20),表示样例个数;
每个样例首先一行是两个整数N和M(1<=N,M<=100000),表示有N个目录和M个询问;
接下来N-1行每行两个目录名A B(目录名是只含有数字或字母,长度小于40的字符串),表示A的父目录是B。
最后M行每行两个目录名A B,表示询问将当前目录从A变成B最少要多少次CD操作。
数据保证合法,一定存在一个根目录,每个目录都能从根目录访问到。

输出:

输入数据第一行包含一个整数T(T<=20),表示样例个数;
每个样例首先一行是两个整数N和M(1<=N,M<=100000),表示有N个目录和M个询问;
接下来N-1行每行两个目录名A B(目录名是只含有数字或字母,长度小于40的字符串),表示A的父目录是B。
最后M行每行两个目录名A B,表示询问将当前目录从A变成B最少要多少次CD操作。
数据保证合法,一定存在一个根目录,每个目录都能从根目录访问到。

样例输入:

2
3 1
B A
C A
B C

3 2
B A
C B
A C
C A

样例输出:

2
1
2

题解:开始只用了map,对于找他们的最近公共祖先 是采用并查集向上搜,当两个相遇时就找到了最近公共祖先了,但是时间复杂度太高了。TLE。。。

于是就只能用tarjan算法来处理LCA问题了。

这里我采用的是tarjan离线LCA算法 + 链式前向星 + map

首先,我们要将题目给你的目录转化成一颗树(利用map),然后求出两个目录的最近父目录在树中的深度,以及我们要转的这个目录的深度,两者相减得到我们要转的目录要经过几步才能到达它和要转成的目录的最近父目录,因为父目录到子目录只需一步,子目录到父目录所需步数就是深度差。对于特殊情况,即我要转成的目录不是我的父目录那么转成另一目录的步数就是到两者最近父目录的深度再加一,否则不用加。而如果两者是一样的,也就是它要转成它自己,那么所需的步数就是0.

对于这棵树的每一个点的深度,我们可以用dfs直接求出来。

然而对于这颗树的任意两个节点的最近父节点,我们就要用到tarjan算法了。

因为要形成一棵树,而n,m最大为10W。所以邻接矩阵是不行的。我们要用邻接表存,这里使用的是链式前向星的数据结构来存树。

tarjan离线LCA算法利用了并查集,它首先要将询问记录下来,它是用一个for循环处理所有询问的,处理的顺序一般和输入的不同。

对于Tarjan离线LCA算法可以参考我这篇文章:

http://blog.csdn.net/ljd4305/article/details/11606865

看一下应该就可以理解了。

我们要处理的就是在找到了一个询问的时候,我们就要将其记录下来,记录的要点包括,两个节点以及两个节点的最近公共祖先。

这里用链式前向星记录询问时,记录下了每个询问的顺序(放在每个询问的结构体里,每个询问包括三个值,两个节点的编号和两者的最近公共祖先),因为我们要按顺序输出,所以我们在存的时候从小到大进行编号。然后当找到了一个询问时,我们就可以将其存放到一个数组里,我们在输出时,只要将这个数组从头到尾输出即可。

大概就三步:

1、建树;

2、dfs得到所有点的深度;

3、tarjan算法求得询问的最近公共祖先,将深度相减,特殊情况考虑进去,输出答案即可。

代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cstring>
using namespace std;

const int MAX_ = 400010;

map<string,int>mp;

struct point {
    int to,next, num;
} edge[MAX_], qedge[MAX_];

struct query {
    int u,v,lca;
} q[MAX_];

int V[MAX_], head[MAX_], d[MAX_], fa[MAX_], ind[MAX_];
bool vis[MAX_];
int M,L, T;
int n, m;

void adde(int from,int to,int c) {
    edge[M].to = to;
    edge[M].num = c;
    edge[M].next = V[from];
    V[from] = M++;
}

void addq(int from,int to,int c) {
    qedge[L].to = to;
    qedge[L].num = c;
    qedge[L].next = head[from];
    head[from] = L++;
}

int find(int x) {
    if(fa[x] == x)return fa[x];
    else return fa[x] = find(fa[x]);
}

void dfs(int k,int pri,int x) {
    d[x] = k;
    for(int i = V[x]; i != -1; i = edge[i].next) {
        if(edge[i].to != pri) {
            dfs(k+1,x,edge[i].to);
        }
    }
}

void tarjan(int x) {
    fa[x] = x;
    vis[x] = 1;
    for(int i = V[x]; i != -1; i = edge[i].next) {
        if(!vis[edge[i].to]) {
            tarjan(edge[i].to);
            fa[edge[i].to] = x;
        }
    }
    for(int i = head[x]; i != -1; i = qedge[i].next) {
        if(vis[qedge[i].to]) {
            q[qedge[i].num].lca = find(qedge[i].to);
        }
    }
}

void solve() {
    for(int i = 1; i <= n; i++) {
        if(ind[i] == 0) {
            dfs(0,-1,i);
            tarjan(i);
            break;
        }
    }
}

int capture(char s[]) {
    if(mp.find(s) == mp.end()) {
        return mp[s] = ++T;
    } else return mp[s];
}

void init() {
    memset(V,-1,sizeof(V));
    memset(head,-1,sizeof(head));
    memset(ind,0,sizeof(ind));
    memset(vis,0,sizeof(vis));
    M = L = T = 0;
    mp.clear();
    for(int i = 0; i <= n; i++) {
        fa[i] = i;
    }
}

void read() {
    int s,t;
    char c1[50],c2[50];
    for(int i = 1; i < n; i++) {
        scanf("%s",c1);
        scanf("%s",c2);
        t = capture(c1);
        s = capture(c2);
        adde(s,t,1);
        adde(t,s,1);
        ind[t]++;
    }
    for(int i = 0; i < m; i++) {
        scanf("%s",c1);
        scanf("%s",c2);
        t = capture(c1);
        s = capture(c2);
        addq(s,t,i);
        addq(t,s,i);
        q[i].u = t;
        q[i].v = s;
    }
}

void print_ans() {
    for(int i = 0; i < m; i++) {
        int t;
        t = d[q[i].u] - d[q[i].lca];
        if(q[i].v != q[i].lca) {
            t++;
        }
        if(q[i].u == q[i].v) t = 0;
        printf("%d\n",t);
    }
}

int main() {
    int Case;
    scanf("%d",&Case);
    while(Case--) {
        scanf("%d%d",&n,&m);
        init();
        read();
        solve();
        print_ans();
    }
    return 0;
}

/*
2
3 1
B A
C A
B C
3 2
B A
C B
A C
C A
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ljd4305/article/details/12351583