goluuuuu's blog

By goluuuuu, history, 6 years ago, In English

Please share implementations for finding the LCA by the method of Binary Lifting. Following one is mine, but I can't seem to figure out what is wrong with it.

int n;
int LOGN;
vector<int> adj[300005];
bool vis[300005];
int tin[300005],tout[300005],d[300005],p[300005];
int dp[300005][19];
vector<int> root;
int timer;
void calc()
{
	LOGN=ceil(log2(n))+1;
	timer=0;
	for(int i=0;i<n;i++)
	{
		tin[i]=0;
		tout[i]=0;
		d[i]=0;
		vis[i]=false;
		for(int j=0;j<LOGN;j++)
		{
			dp[i][j]=-1;
		}
	}
}
void dfs(int v,int parent){
	if(parent!=-1)
		d[v]=d[parent]+1;
	p[v]=parent;
	tin[v]=++timer;
	vis[v]=true;
	dp[v][0] = parent;
	for (int i = 1; i <= LOGN; ++i)
	{
		if(dp[v][i-1]==-1)
			dp[v][i]=-1;
		else
			dp[v][i] = dp[dp[v][i-1]][i-1];
	}        	
	for(auto u : adj[v])
	{
		if(!vis[u])
		{
			dfs(u,v);
		}
	}
	tout[v]=++timer;
}
bool is_ancestor(int u,int v){// is v ancestor of u?
	if(tin[u]>=tin[v] && tout[u]<=tout[v])
		return true;
	return false;
}
int LCA(int u,int v){
	if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = LOGN; i >= 0; i--) {
        if (!is_ancestor(dp[u][i], v))
            u = dp[u][i];
    }
    return dp[u][0];
}
void solve()
{
    cin>>n;
	rep(i,0,n)
	{
		int m;
		cin>>m;
		rep(j,0,m){
			int child;
			cin>>child;
			adj[i].pb(child);
			adj[child].pb(i);
		}
	}
	calc();
	dfs(0,-1);
	int query;
	cin>>query;
	rep(i,0,query){
		int u,v;
		cin>>u>>v;
		cout<<LCA(u,v)<<endl;
	}    
}
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Here are my (basic) templates.

Binary Lifting

LCA

  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    Thank you so much! If you don't mind, can you spot the mistake in my code?

    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it +12 Vote: I do not like it

      In the lines

      Spoiler

      it should be return v and return u respectively. You've returned it the other way around.

      • »
        »
        »
        »
        6 years ago, hide # ^ |
         
        Vote: I like it +12 Vote: I do not like it

        Thank you so much sir!

        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it +10 Vote: I do not like it

          No problem! For future reference, when linking long code, either put it in a spoiler or use something like pastebin or IDEone (this is preferred), to stop your post from being annoying to read :) That might explain the downvotes on the post.

      • »
        »
        »
        »
        5 years ago, hide # ^ |
         
        Vote: I like it +6 Vote: I do not like it

        That is so kind of you! To have gone ahead and answered a genuine doubt inspite of most others downvoting it. I have nothing to do with this post, I was looking for something else but just accidentally chanced upon this. Thought I'd stop by and appreciate your kind gesture. You're awesome!