最近公共祖先问题,求的是中两个节点的最近公共祖先。使用了一个带并查集的离线算法。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 10005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int p[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void make ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[i] = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( p[a] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return a;
}
int r = find ( p[a] );
p[a] = r;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un ( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ra = find ( a );
int rb = find ( b );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p[rb] = ra;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int c;/**//*记录结点的入度*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int last;/**//*记录最后一个节点的地址*/
int next;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
}tab[LEN];/**//*邻接链表头,记录最后一个节点的地址*/
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int num;
int next;
}type;
type node[LEN*2];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int next1; /**//*下一个可以使用的位置*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initm ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next1 = 0;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tab[i].c = 0;
tab[i].last = -1;
tab[i].next = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void adde ( int b, int e )/**//*增加一条边*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
node[next1].num = e;
node[next1].next = -1;
if ( tab[b].next >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
node[ tab[b].last ].next = next1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tab[b].next = next1;
}
tab[b].last = next1;
tab[e].c ++;
next1 ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int next;
int last;
}que[LEN];
type q[LEN*2];
int next2;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initq ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next2 = 0;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
que[i].last = -1;
que[i].next = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void addq ( int b, int e )/**//*增加一条边*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
q[next2].num = e;
q[next2].next = -1;
if ( que[b].next >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
q[ que[b].last ].next = next2;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
que[b].next = next2;
}
que[b].last = next2;
next2 ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int color[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initc ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
color[i] = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void lca ( int p )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=tab[p].next; i!=-1; i=node[i].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
lca ( node[i].num );
un ( p, node[i].num );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=que[p].next; i!=-1; i=q[i].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( color[ q[i].num ] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "%d\n", find ( q[i].num ) + 1 );
}
}
color[p] = 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
int n;
int b, e;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf ( "%d", &t );
while ( t -- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d", &n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
initm ( n );
for ( int i=0; i<n-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d%d", &b, &e );
adde ( b-1, e-1 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
initq ( n );
scanf ( "%d%d", &b, &e );
addq ( b-1, e-1 );
addq ( e-1, b-1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
initc ( n );/**//*初始化颜色*/
make ( n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! tab[i].c )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
lca ( i );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1330