最近公共祖先LCA

//最近公共祖先 LCA //DFS + ST 在线算法 //算法思想：对一棵树进行深搜回溯标号，那么两个节点的最近公共祖先就是两个节点第一次标号之间深度最小（非标号，因为回溯会增大那个节点，虽然该节点第一次标号很小）的那个对应的节点 //poj1330 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> using namespace std ; const int maxn = 1e4 + 10 ; int rmq[ 2* maxn ] ; int dp[maxn * 2 ][20 ] ; void RMQ(int n ){ for( int i = 1 ;i<= n ;i++) dp[i][0] = i ; for ( int j = 1 ; j<= 20 ;j ++) for(int i = 1 ; i + ( 1<<(j-1)) <= n ;i ++) dp[i][j]= rmq[ dp[i][j - 1] ] < rmq[ dp[i + ( 1<<( j-1 ) )][ j-1] ] ? dp[i][j-1] :dp[i + ( 1<<(j-1) )][j-1] ; // dp[i][j]= rmq[ dp[i][j - 1] ] < rmq[ dp[i + ( 1<<( j-1 ) )][ j-1] ] ? dp[i][j-1] :dp[i + (1<<(j-1))][j-1]; } //给出两个节点第一次的标号，返回最近公共祖先的标号 int query(int i , int j ){ if( i> j ) swap( i , j ) ; int k = log10( j - i + 1.0) / log10 (2.0) ; return ( rmq[ dp[i][ k ] ] <= rmq[ dp[j - ( 1<<k ) + 1][ k] ] )? dp[i][k] : dp[j - ( 1<<k ) + 1 ][i] ; } struct Edge{ int to , next ; }edge[ maxn * 2 ]; int tot , head [maxn ] ; int F[maxn * 2 ] ; int P[maxn] ; int cnt ; void ini(){ tot = 0 ; memset( head , -1 , sizeof(head )) ; } void addedge( int u , int v ){ edge[tot ].to = v ; edge[tot].next = head[u] ; head[u] = tot ++ ; } //当前节点u，父节点pre，深度dep void dfs( int u , int pre , int dep){ //标号是++cnt的值是 u F[ ++cnt ] = u ; //标号为cnt的节点的深度 rmq [cnt ] = dep ; //当前节点u标号cnt P[u] = cnt ; for( int i = head[u] ; i!= -1 ;i=edge[i].next ){ int v = edge[i].to ; if( v == pre ) continue ; //遍历子节点 dfs( v , u , dep + 1 ) ; F[ ++ cnt ] = u ; rmq[cnt ] = dep ; } } void iniLca( int root , int num ){ cnt = 0 ; dfs( root , root , 0) ; RMQ( 2 *num -1 ) ; } int queryLca( int u , int v ){ int x = query( P[u] , P[v ]) ; return F[ x ] ; } bool flag [maxn] ; int main(){ int T , N , u , v ; scanf("%d" , &T) ; while( T-- ){ scanf("%d" , & N ) ; ini() ; memset( flag , false , sizeof( flag )) ; for( int i = 1 ;i<N ;i++){ scanf("%d%d" , & u , & v ) ; addedge( u , v ) ; addedge( v , u ) ; flag[v] = true ; } //有根树找出根节点 int root ; for( int i = 1;i<=N ;i++){ if( !flag[i] ){ root = i ; break ; } } iniLca( root , N ) ; scanf("%d%d" , & u , & v ) ; printf("%d\n" , queryLca( u , v ) ) ; } return 0 ; } //LCA在线算法 //倍增法 //POJ1330 //倍增法思想：首先获得任意节点第2^i个祖父节点的fa数组 //对于给定的两个点，对于其中最浅的那个节点，对最深的那个节点取他和最浅的节点相同一层的父节点 //如果该父节点和最浅的节点相同，则代表最浅的节点是最深的节点的最近公共祖先 //否则，通过fa数组不断将两个节点按照各自的路径上浮，直到他们是一个节点的两个子节点，那么这个父节点就是原来两个点的最近公共祖先 #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> using namespace std ; const int maxn = 1e4 + 10 ; const int DEG = 20 ; struct Edge{ int to , next ; }edge[maxn* 2]; int head[maxn] , tot ; void addedge( int u , int v ){ edge[tot].to = v ; edge[tot].next = head[u] ; head[u] = tot ++ ; } void init(){ tot = 0 ; memset( head , -1 , sizeof( head )) ; } //节点i的第2^i个祖先 int fa[maxn][DEG] ; //深度 int deg[maxn] ; void dis(){ for( int i = 1 ;i<= 20 ;i++){ for( int j = 0 ;j<20 ;j++) cout<<fa[i][j] <<" "; cout<<endl; } } void BFS( int root ){ queue<int> que ; deg[ root ] = 0 ; fa[ root ][0] = root ; que.push( root ) ; while( !que.empty() ){ int tmp = que.front() ; que.pop() ; for( int i = 1 ;i<DEG ; i++){ fa[tmp][i] = fa[ fa[tmp][i-1] ][ i-1 ] ; } for( int i = head[tmp ] ; i!= -1 ; i= edge[i].next ){ int v = edge[i].to ; if( v == fa[tmp][0] ) continue ; deg[v] = deg[tmp] + 1 ; fa[v][0] = tmp ; que.push( v ) ; } } } int LCA( int u , int v ){ if( deg[u] > deg[v] ) swap( u , v ) ; int hu = deg[u] , hv = deg[v] ; int tu = u , tv = v ; cout<<hu<<" "<<hv<<endl; cout<<tu<<" "<<tv<<endl; //tv和tu同一层的祖父节点 for( int det = hv - hu , i = 0 ; det ; det >>= 1, i ++) if( det & 1) tv = fa[tv][i] ; cout<<tu<<" "<<tv<<endl; //tv是tu的同一路径上的孙子子节点 if( tu == tv ) return tu ; //寻找同一层的两个节点tv和tu的公共祖先 for( int i = DEG -1 ; i>= 0 ; i--){ if( fa[tu][i] == fa[tv][i]) continue ; //tu和tv不断上浮但是一直处于同一层 tu = fa[tu][i] ; tv = fa[tv][i] ; } //tu和tv处于同一层并且是一个父节点的两个子节点，任取tu或者tv的父节点 return fa[tu][0] ; } bool flag[maxn] ; int main(){ int T , n , u , v ; scanf("%d" , & T ) ; while( T -- ){ scanf("%d" , & n) ; init() ; memset( flag , false , sizeof( flag )) ; for( int i =1 ; i<n ;i++){ scanf("%d%d" , & u , & v ); addedge( u , v ) ; addedge( v , u ) ; flag[v] = true ; } int root ; for( int i = 1 ;i<= n ;i++) if( !flag[i] ){ root = i ; break ; } BFS( root ) ; // dis() ; scanf("%d%d" , & u , & v ) ; printf("%d\n" , LCA( u , v )) ; } return 0 ; } //最近公共祖先LCA //离线算法 ： Tarjan //POj1330 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std ; const int maxn = 1e4 + 10 ; const int maxm = 1e5 + 10 ; int F[maxn] ; int find( int x ){ if( F[x] == -1 ) return x ; return F[x] = find( F[x] ) ; } void bing( int u , int v ){ int t1 = find( u ) ; int t2 = find( v ) ; if( t1 != t2 ) F[t1] = t2 ; } bool vis[maxn] ; int ancestor[maxn] ; struct Edge{ int to , next ; }edge[maxn* 2 ]; int head[maxn] , tot ; void addedge( int u , int v ){ edge[tot].to = v ; edge[tot].next = head[u] ; head[u] = tot ++ ; } struct Query{ int q , next ; int index ; }query[maxm* 2 ]; int answer[maxm] ; int h[maxm ] ; int tt , Q ; void add_query( int u , int v , int index ){ query[tt].q = v ; query[tt].next = h[u] ; query[tt].index = index ; h[u] = tt ++ ; query[tt].q = u ; query[tt].next = h[v] ; query[tt].index = index ; h[v] = tt ++ ; } void init(){ tot = 0 ; tt = 0 ; memset( head , -1 , sizeof( head )) ; memset( h , -1 , sizeof( h )) ; memset( vis , false , sizeof(vis )) ; memset( F , -1 , sizeof( F)) ; memset( ancestor , 0 , sizeof( ancestor)) ; } void LCA( int u ){ ancestor[u] = u ; vis[u] = true ; for( int i = head[u] ; i!= -1 ;i=edge[i].next ){ int v = edge[i].to ; if( vis[v]) continue ; LCA( v ) ; bing( u , v ) ; ancestor[ find( u ) ] = u ; } for( int i= h[u] ; i!= -1 ; i= query[i].next ){ int v = query[i].q ; if( vis[v] ) answer[query[i].index ] = ancestor[ find(v ) ] ; } } bool flag[maxn] ; int main(){ int n , u , v , k ; scanf("%d" , & n) ; while( n -- ){ init() ; scanf("%d" , & k ) ; memset( flag , false , sizeof( flag )) ; for( int i = 1 ;i< k ;i++){ scanf("%d%d" , & u , & v ) ; addedge( u , v ) ; addedge( v , u ) ; flag[v ] = true ; } scanf("%d%d" , & u , & v ) ; add_query( u ,v , 0 ) ; int root ; for( int i = 1 ;i<= k ;i++) if( !flag[i] ){ root = i ; break ; } LCA( root ) ; cout<<answer[0]<<endl; } return 0 ; }