牛客 小米 小米Git LCA最近公共祖先 倍增

這道題很明顯的LCA了

1. 一般求LCA方法

• 先建樹,求 U , V U,V U,V的 L C A LCA LCA
• 如果 U 和 V U和V U和V深度不相同,先把深的那個點向上爬到同一層
• 如果已經跳到相同層了,就 U , V U,V U,V一起向上跳,直到 U = = V U==V U==V

2. 倍增求LCA O ( n l o g n ) O(nlogn) O(nlogn)

• 在1的基礎上改進,引入了一個預處理好的表來記錄往上跳 2 0 , 2 1 , 2 2 . . . 2 k 2^0,2^1,2^2...2^k 20,21,22...2k步的祖先
• 需要先 d f s dfs dfs把這個表預處理出來(可以在建樹的時候就預處理出跳表)

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