Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

提供一个简单的思路,没有复杂的数据结构和算法哦~

Posted by dahai1990 at 2012-11-28 11:08:52 on Problem 1330
问题就是求x和y的最近公共祖先。
思路:把x到根节点的路径标记一下,然后去搜y到根节点的路径,碰到的第一个就是答案了。具体实现看代码:

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=10005;
int vis[maxn],p[maxn];
int main()
{
    int T,n,i,x,y;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(vis,0,sizeof(vis));
        memset(p,0,sizeof(p));
        for(i=1;i<n;i++)
        {
            cin>>x>>y;
            p[y]=x;
        }
        cin>>x>>y;
        while(x){
            vis[x]=1;
            x=p[x];
        }
        while(y){
            if(vis[y]) break;
            y=p[y];
        }
        cout<<y<<endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator