前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >poj----1330Nearest Common Ancestors(简单LCA)

poj----1330Nearest Common Ancestors(简单LCA)

作者头像
Gxjun
发布2018-03-26 14:40:13
6980
发布2018-03-26 14:40:13
举报
文章被收录于专栏:ml

题目连接  http://poj.org/problem?id=1330

就是构建一棵树,然后问你两个节点之间最近的公共父节点是谁?

代码:

代码语言:javascript
复制
 1 /*Source Code
 2 Problem: 1330        User: huifeidmeng
 3 Memory: 1232K        Time: 63MS
 4 Language: C++        Result: Accepted
 5 
 6     Source Code
 7 */
 8     #include<iostream>
 9     #include<vector>
10     #include<cstdio>
11     #include<cstring>
12     #include<cstdlib>
13     using namespace std;
14     const int maxn=10002;
15     vector<int> tree[maxn],qus[maxn];
16     int rank[maxn],father[maxn];
17     bool vis[maxn];
18     int rudu[maxn];
19     int lroot[maxn];
20     void init(int n){
21          memset(vis,0,sizeof(vis));
22          memset(rudu,0,sizeof(rudu));
23          memset(lroot,0,sizeof(lroot));
24         for(int i=1;i<=n;i++){
25             father[i]=i;
26             rank[i]=1;
27             tree[i].clear();
28             qus[i].clear();
29         }
30     }
31     int find(int a){
32        while(a!=father[a])
33              a=father[a];
34         return a;
35     }
36     void Union(int a,int b)
37     {
38         int x=find(a);
39         int y=find(b);
40         if(x==y) return ;
41         if(rank[x]<rank[y]){
42           rank[y]+=rank[x];
43           father[x]=y;
44         }
45         else {
46          rank[x]+=rank[y];
47          father[y]=x;
48         }
49     }
50     void LCA(int u)
51     {
52       lroot[u]=u;
53       int len=tree[u].size();
54       for(int i=0;i<len;i++){
55           LCA(tree[u][i]);
56           Union(u,tree[u][i]);
57           lroot[find(u)]=u;
58       }
59       vis[u]=1;
60       int ss=qus[u].size();
61       for(int i=0;i<ss;i++){
62             if(vis[qus[u][i]]){
63                 printf("%d\n",lroot[find(qus[u][i])]);
64                 return ;
65             }
66       }
67     }
68     int main()
69     {
70       int cas,n,u1,u2;
71       //freopen("test.in","r",stdin);
72       scanf("%d",&cas);
73       while(cas--){
74           scanf("%d",&n);
75           init(n);
76           for(int i=1;i<n;i++){
77           scanf("%d%d",&u1,&u2);
78           tree[u1].push_back(u2);
79           rudu[u2]++;  
80           }
81           scanf("%d%d",&u1,&u2);
82           qus[u1].push_back(u2);
83           qus[u2].push_back(u1);
84           for(int i=1;i<=n;i++){
85          if(0==rudu[i]){ //找到root
86            LCA(i);
87            break;
88           }
89           }
90       }
91     return 0;
92     }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-09-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档