poj 1330 Nearest Common Ancestors（LCA：最近公共祖先）

多校第七场考了一道lca，那么就挑一道水题学习一下吧= =

最简单暴力的方法：建好树后，输入询问的点u，v，先把u全部的祖先标记掉，然后沿着v->rt（根）的顺序检查，第一个被u标记的点即为u，v的公共祖先。

标记的时候又犯老毛病了：while，do while都不对，最后还是while（1）了T^T

 #include<cstdio>

 #include<cstring>

 const int MAXN=;

 int p[MAXN],vis[MAXN];

 int main()

 {

     int T,n,u,v;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         memset(vis,,sizeof(vis));

         memset(p,-,sizeof(p));

         for(int i=;i<n-;i++){

             scanf("%d%d",&u,&v);

             p[v]=u;

         }

         scanf("%d%d",&u,&v);

         while()

         {

             vis[u]=;

             if(p[u]==-)

                 break;

             u=p[u];

         }

         while(vis[v]!=)

             v=p[v];

         printf("%d\n",v);

     }

     return ;

 }

 /*

 10

 3

 1 2

 1 3

 2 3

 */

然后是tarjin了：

自己先照着推了一遍代码，才把图示给看明白：http://www.csie.ntnu.edu.tw/~u91029/LowestCommonAncestor.html

可以处理多组询问

因为是以dfs为框架，所以先处理子树，依次将当前点u的每棵子树加入当前点的集合，之后对当前点进行询问（u，v）。若v已被标记，由于是dfs，所以最近公共祖先包含v的子树必然已经完成了搜索，那么v所在集合的祖先 find(v) 就是询问（u，v）的解。又因为是dfs，所以子树内的询问必然已经完成。

注意：询问（u，v）要正反向各加一遍，因为标记vis有先后顺序，而我们不清楚u，v的被访问的顺序。搜索到u时v尚未被标记，会放弃此次询问。所以不必担心同一次询问被完成了两次，其中一次会被舍弃。

关键是要理解先处理dfs，再合并集合。

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #define clr(a,m) memset(a,m,sizeof(a))

 #define rep(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int MAXN=;

 struct Edge{

     int v,next;

     Edge(){}

     Edge(int _v,int _next):v(_v),next(_next){}

 }edge[MAXN<<];

 vector<int>query[MAXN];

 int p[MAXN],vis[MAXN],ancestor[MAXN];

 int head[MAXN],tol;

 void init(int n)

 {

     tol=;

     clr(head,-);

     rep(i,,n){

         query[i].clear();

     }

 }

 void add(int u,int v)

 {

     edge[tol]=Edge(v,head[u]);

     head[u]=tol++;

 }

 int build(int n)

 {

     int u,v;

     init(n);

     clr(vis,);

     rep(i,,n-){

         scanf("%d%d",&u,&v);

         vis[v]=;

         add(u,v);

     }

     rep(i,,){

         scanf("%d%d",&u,&v);

         query[u].push_back(v);

         query[v].push_back(u);

     }

     rep(i,,n)

         if(!vis[i])

             return i;

 }

 int find(int x)

 {

     return (x==p[x])?x:(p[x]=find(p[x]));

 }

 void dfs(int x)

 {

     vis[x]=;

     for(int i=head[x];i!=-;i=edge[i].next)

     {

         int v=edge[i].v;

         dfs(v);

         p[v]=x;

     }

     int siz =query[x].size()-;

     rep(i,,siz)

     {

         if(vis[query[x][i]]){

             printf("%d\n",find(query[x][i]));

             return ;

         }

     }

 }

 void LCA(int rt,int n)

 {

     clr(vis,);

     rep(i,,n)

         p[i]=i;

     dfs(rt);

 }

 int main()

 {

     int T,n,u,v;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         int rt=build(n);

         LCA(rt,n);

     }

     return ;

 }

有一点要注意的：query[x].size()的返回值竟然不是 int 型的= = ，不信可以把 siz 省略掉，在循环内打印一下，惊喜的发现 for(int i=0;i<-1;i++) 这种东西竟然能够进入循环。强制转换（int）也能解决。

再附上一段代码，是实现全部询问的，当然不适合这道题，MAXN=11111，MLE我竟然还反应了半天。。

 void dfs(int x,int n)

 {

     vis[x]=;

     for(int y=head[x];y!=-;y=edge[y].next)

     {

         int v=edge[y].v;

         dfs(v,n);

         p[v]=x;

     }

     rep(y,,n)

         if(vis[y])

             lca[x][y]=lca[y][x]=find(y);

 }

巴特西

poj 1330 Nearest Common Ancestors（LCA：最近公共祖先）

最新文章

热门文章