SPOJ LCA Solution

| July 01, 2015

The correct, optimal and working solution for programming question LCA on spoj

#include <stdio.h>
#include <stdlib.h>

int lca ( int a , int b , int * height , int * parent , int n ) {

	if ( height[a] > height[b] ) {
		int t;
		t = a;
		a = b;
		b = t;
	}

	int pa = a , pb = b;

	while ( height[pa] != height[pb] ) {
		pb = parent[pb];
	}

	if ( pa == pb )
		return pa;

	while ( parent[pa] != parent[pb] ) {
		pa = parent[pa];
		pb = parent[pb];
	}

	if ( parent[pa] == 0 )
		return pa;
	else
		return parent[pa];
}

int main( int argc , char * argv[] ) {

	int t , i , z;
	scanf("%d" , &t);

	for ( z = 1; z <= t ; z++ ) {
		printf("Case %d:\n" , z);

		int n , i , j;
		int * height;
		int * parent;
		scanf("%d" , &n);

		height = ( int * ) calloc ( n+1 , sizeof(int) );
		parent = ( int * ) calloc ( n+1 , sizeof(int) );

		for ( i = 1 ; i <= n ; i++ ) {
			int k , l;
			scanf("%d" , &k);
			while ( k-- ) {
				scanf("%d" , &l);
				height[l] = height[i]+1;
				parent[l] = i;
			}
		}

		int k;
		scanf("%d" , &k);

		while ( k-- ) {
			int a,b;
			scanf("%d%d" , &a,&b);

			printf("%d\n" , lca( a,b, height , parent , n ));

		}

		free(height);
		free(parent);

	}

	return 0;
}