LCA最近公共祖先问题 倍增
小米Git
http://www.nowcoder.com/questionTerminal/e9ff41269a7e49519b87fe7d9fd0d477
这道题很明显的LCA了
- 一般求LCA方法
- 先建树,求
的
- 如果
深度不相同,先把深的那个点向上爬到同一层
- 如果已经跳到相同层了,就
2. 倍增求LCA
在1的基础上改进,引入了一个预处理好的表来记录往上跳
步的祖先
需要先
把这个表预处理出来(可以在建树的时候就预处理出跳表)
void dfs_build(vector<string>& mtx, int u, int father) { vis[u] = true; level[u] = level[father]+1; //更新当前递归到的点的深度 up[u][0] = father; //向上跳2^0=1,就是跳到爹上 for(int i=1; (1<<i)<=level[u]; i++) //2^j = (2^j-1) + 2^(j-1) up[u][i] = up[up[u][i-1]][i-1]; for(int i=0; i<n; i++) { int v = i; if(v == u || vis[v] || mtx[u][v] == '0') continue ; fa[v] = u; //建立父子关系 dfs_build(mtx, v, u); } }求LCA
int lca(int u, int v) { if(level[u] > level[v]) swap(u, v); for(int i=L; i>=0; i--) if(level[u] <= level[v]-(1<<i)) v = up[v][i]; if(u == v) return u; for(int i=L; i>=0; i--) if(up[u][i] == up[v][i]) continue ; else { u = up[u][i]; v = up[v][i]; } return up[u][0]; }
3. Tarjan求LCA (离线算法)
不会
本题代码
#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN (2048)
#define ll long long
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
using namespace std;
#define show(x...) \
do { \
cout << "\033[31;1m " << #x << " -> "; \
err(x); \
} while (0)
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
namespace FastIO {
char print_f[105];
void read() { }
void print() { putchar('\n'); }
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth) {
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch)) {
if (ch == '-') f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
read(oth...);
}
template <typename T, typename... T2>
inline void print(T x, T2... oth) {
ll p3=-1;
if(x<0) putchar('-'), x=-x;
do{
print_f[++p3] = x%10 + 48;
} while(x/=10);
while(p3>=0) putchar(print_f[p3--]);
putchar(' ');
print(oth...);
}
} // namespace FastIO
using FastIO::print;
using FastIO::read;
int n, m, Q, K;
#if 0 //非倍增的普通求LCA
bool vis[MAXN];
int level[MAXN], fa[MAXN]; //fa[i]表示i的父节点
#define cls(x) (memset(x, false, sizeof(x)))
class Solution {
public:
int n;
void init(vector<string>& mtx) {
n = mtx.size();
cls(level), cls(fa), cls(vis);
}
void dfs_build(vector<string>& mtx, int u, int dep) {
vis[u] = true;
level[u] = dep; //更新当前递归到的点的深度
for(int i=0; i<n; i++) {
int v = i;
if(v == u || vis[v] || mtx[u][v] == '0') continue ;
fa[v] = u; //建立父子关系
dfs_build(mtx, v, dep+1);
}
}
int getSplitNode(vector<string>& mtx, int u, int v) {
init(mtx);
dfs_build(mtx, 0, 0); //先dfs建树
int lu = level[u], lv = level[v];
while(lu < lv) //把u和v爬到同一层
lv = level[fa[v]], v = fa[v];
while(lv < lu)
lu = level[fa[u]], u = fa[u];
while(u != v) //u和v一起向上爬
u = fa[u], v = fa[v];
return u;
}
};
#else //倍增求LCA
#define L (20)
bool vis[MAXN];
int level[MAXN], fa[MAXN]; //fa[i]表示i的父节点
int up[MAXN][L+5]; //跳表
#define cls(x) (memset(x, false, sizeof(x)))
class Solution {
public:
int n;
void init(vector<string>& mtx) {
n = mtx.size();
cls(level), cls(fa), cls(vis), cls(up);
}
void dfs_build(vector<string>& mtx, int u, int father) {
vis[u] = true;
level[u] = level[father]+1; //更新当前递归到的点的深度
up[u][0] = father; //向上跳2^0=1,就是跳到爹上
for(int i=1; (1<<i)<=level[u]; i++) //2^j = (2^j-1) + 2^(j-1)
up[u][i] = up[up[u][i-1]][i-1];
for(int i=0; i<n; i++) {
int v = i;
if(v == u || vis[v] || mtx[u][v] == '0') continue ;
fa[v] = u; //建立父子关系
dfs_build(mtx, v, u);
}
}
int lca(int u, int v) {
if(level[u] > level[v]) swap(u, v);
for(int i=L; i>=0; i--)
if(level[u] <= level[v]-(1<<i))
v = up[v][i];
if(u == v) return u;
for(int i=L; i>=0; i--)
if(up[u][i] == up[v][i]) continue ;
else {
u = up[u][i];
v = up[v][i];
}
return up[u][0];
}
int getSplitNode(vector<string>& mtx, int u, int v) {
init(mtx);
#if 0
fori(0, n-1)
forj(0, n-1)
if(mtx[i][j] == '1') printf("%d %d\n", i, j);
#endif
dfs_build(mtx, 0, 0); //先dfs建树
#if 0
forarr(level, 0, n-1, "level");
forarr(fa, 0, n-1, "fa ");
#endif
return lca(u, v);
}
};
#endif
#if 1
int main() {
#ifdef debug
freopen("test", "r", stdin);
// freopen("out_main", "w", stdout);
clock_t stime = clock();
#endif
vector<string> mtx = {
"0110000000","1000101000","1001000000","0010000000","0100000101",
"0000001000","0100010010","0000100000","0000001000","0000100000"
};
Solution s;
int U = 6, V = 7;
cout << s.getSplitNode(mtx, U, V);
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}
#endif
