hihoCoder 最近公共祖先2 之 DFS + 并查集 法

第一次玩 hihoCoder, 题目就是一个裸的 LCA  问题, 只不过结点的名字不是数字而是字符串, 用两个 map 映射一下就可以转化为数字来处理.

以前做 LCA 都是用的 Tarjan 离线算法, 这次 hihoCoder 给出一种 dfs + 并查集大法, 我颇为好奇. 然后 AC 了之后 Google 了一下 Tarjan 离线算法(太久没做 LCA的题目忘了 Tarjan 长啥样了), 发现其实 hohoCoder 只是没提到 Tarjan 这个名词, 本质都是一样的算法呐!

在这道题中, 离线算法的好处体现在:

• 如果用传统在线算法, 对于询问 (u, v) 需要找到 u–>root 的路径和 v–>root 的路径, 然后就能找到 answer. 但是这个回溯的过程是 O(N), 如果有 M 个询问, 整个复杂度就是 O(NM). 离线算法解决了这个问题, 在 dfs 的过程中, 碰到和谁相关的询问就立马给他一个回答, 理论复杂度是 O(N).

但是由于我没想好如何快速找到和当前 dfs 到的结点 u 相关的询问, 我第一次枚举了每一个询问来查找, 最后就超时了. 然后我给那些询问建立了一个 map<int, vector<int> >, 这样能优化不少, 最后 AC, 但是不知道有没有更快的方法, 因为这样的速度虽然接近 O(N), 但是还是达不到.

代码如下:

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e5 + 10;

int n, m, cnt;
map<string, int> getId;
map<int, string> getName;
map<int, vector<int> > queque;
pair<string, string> queries[maxn];
string answers[maxn];
vector<int> G[maxn];
int ufa[maxn];
int degree[maxn];   // find the tree's root
int color[maxn];

/////////////////

int findroot(int x) {
  if (ufa[x] == x) return x;
  else return ufa[x] = findroot(ufa[x]);
}

void dfs(int fa, int u) {
  for (int i = 0; i < queque[u].size(); i++) {
    int j = queque[u][i];
    if (answers[j] != "") continue;   // already answered
    if (queries[j].first == queries[j].second) {
      answers[j] = queries[j].first;
    } else if (getId[queries[j].first] == u && color[getId[queries[j].second]]) {
      answers[j] = getName[findroot(getId[queries[j].second])];
    } else if (getId[queries[j].second] == u && color[getId[queries[j].first]]) {
      answers[j] = getName[findroot(getId[queries[j].first])];
    }
  }

  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    color[v] = 1;
    dfs(u, v);
    ufa[findroot(v)] = findroot(u);
    color[v] = 2;
  }
}

void solve() {
  int start = 0;
  for (int i = 1; i <= cnt; i++) {
    if (degree[i] == 0) {
      start = i;
      break;
    }
  }

  color[start] = 1;
  dfs(-1, start);
  color[start] = 2;

  for (int i = 0; i < m; i++) {
    cout << answers[i] << endl;
  }
}

void addedge(string fa, string u) {
  G[getId[fa]].push_back(getId[u]);   // fa --> u
  degree[getId[u]]++;
}

int main() {
  n = gint();
  cnt = 1;
  for (int i = 1; i <= n; i++) {
    ufa[i] = i;
    string a, b;
    cin >> a >> b;
    if (getId[a] == 0) {
      getId[a] = cnt;
      getName[cnt] = a;
      cnt++;
    }

    if (getId[b] == 0) {
      getId[b] = cnt;
      getName[cnt] = b;
      cnt++;
    }

    addedge(a, b);
  }

  cnt--;

  m = gint();
  for (int i = 0; i < m; i++) {
    string a, b;
    cin >> a >> b;
    queque[getId[a]].push_back(i);
    queque[getId[b]].push_back(i);
    queries[i] = make_pair(a, b);
  }
  solve();
  return 0;
}



/*

4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin

*/