poj 1330 (简单LCA)

题意:现实给你一棵树然后给你树上的n-1条边,接着给你一对顶点,然后让你求这对顶点的LCA。

思路:由于刚刚学习LCA所以找了这一道最最水的LCA题目来做发现用复杂度较高的算法也能过,就是先遍历求出每个结点的父亲和深度,然后再将深度深的向上走,一直走到两个结点在同一高度上。再两个节点一起往上走,直到走到一个节点那么这个节点即为那两个节点的LCA。

代码如下:

poj 1330 (简单LCA)
 1 //LCA
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 
16 using namespace std;
17 
18 typedef long long ll;
19 typedef pair<int ,int> pii;
20 typedef pair<unsigned int, unsigned int> puu;
21 typedef pair<int ,double> pid;
22 typedef pair<ll, int> pli;
23 
24 const int INF = 0x3f3f3f3f;
25 const double eps = 1e-6;
26 const int LEN = 100000+10;
27 vector<int> Map[LEN];
28 int root, ind[LEN], depth[LEN], parent[LEN];
29 
30 void dfs(int v, int p, int d){
31     parent[v] = p;
32     depth[v] = d;
33     for(int i=0; i<Map[v].size(); i++){
34         if(Map[v][i] != p)dfs(Map[v][i], v, d+1);
35     }
36 }
37 
38 void init() {dfs(root, -1, 0);}
39 
40 int lca(int u, int v){
41     while(depth[u] > depth[v]) u = parent[u];
42     while(depth[v] > depth[u]) v = parent[v];
43     while(u!=v){
44         u = parent[u];
45         v = parent[v];
46     }
47     return u;
48 }
49 
50 int main()
51 {
52 //    freopen("in.txt", "r", stdin);
53 
54     int n, a, b, T;
55     scanf("%d", &T);
56     while(T--){
57         for(int i=0; i<LEN; i++)Map[i].clear();
58         memset(ind, 0, sizeof ind);
59         scanf("%d", &n);
60         for(int i=0; i<n-1; i++){
61             scanf("%d%d", &a, &b);
62             Map[a].PB(b);
63             Map[b].PB(a);
64             ind[b]++;
65         }
66         for(int i=1; i<=n; i++)
67             if(ind[i]==0) {root = i;break;}
68         init();
69         scanf("%d%d", &a, &b);
70         int ans = lca(a, b);
71         printf("%d\n", ans);
72     }
73     return 0;
74 }
View Code

poj 1330 (简单LCA)

上一篇:用Canvas玩3D:点-线-面


下一篇:JDK中的URLConnection参数详解