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
代码如下:
/**
* 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
*/