MYF

POJ 1330 Nearest Common Ancestors

Posted on | In | | Visitors

题目链接

POJ 1330

方法：LCA最近公共祖先算法

题目分析

题目大意

前n-1行建树，询问第n行的两个点的最近公共祖先

解析

模版题。

代码

LCA->RMQ问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
//DFS + RMQ 在线算法
struct node
{
    int x;
};
vector<node> V[maxn];
int E[maxn * 2], D[maxn * 2], first[maxn], vis[maxn], dis[maxn], n, m, top = 1,root[maxn],st;
int dp[30][maxn * 2];
void init()
{
    top=1;
    memset(root,0,sizeof(root));
    memset(vis,0,sizeof(vis));
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        V[i].clear();
    int a, b;
    node tmp;
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d%d", &a, &b);
        tmp.x = b;
        V[a].push_back(tmp);
        tmp.x = a;
        V[b].push_back(tmp);
        root[b]=1;
    }
    for(int i=1; i<=n; i++)
        if(root[i]==0)
        {
            st=i;
            break;
        }
}
void dfs(int u, int dep)
{
    vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++;
    for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x])
    {
        int v = V[u][i].x;
        dfs(v, dep + 1);
        E[top] = u, D[top++] = dep;
    }
}
void ST(int num)
{
    for (int i = 1; i <= num; i++) dp[0][i] = i;
    for (int i = 1; i <= log2(num); i++)
        for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num)
        {
            int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)];
            if (D[a] < D[b]) dp[i][j] = a;
            else dp[i][j] = b;
        }
}
int RMQ(int x, int y)
{
    int k = (int) log2(y - x + 1.0);
    int a = dp[k][x], b = dp[k][y - (1 << k) + 1];
    if (D[a] < D[b]) return a;
    return b;
}
int main ()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        dfs(st, 0);
        ST(top);
        int x, y;
        scanf("%d%d", &x, &y);
        int a = first[x], b = first[y];
        if (a > b) swap(a, b);
        int pos = RMQ(a, b);
        printf("%d\n",E[pos]);
    }
    return 0;
}

Tarjan离线算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int pre[maxn],point[maxn],point2[maxn];
bool vis[maxn];
struct Edge
{
    int v;///连接点
    int next;///下一条从此边的出发点发出的边
} edge[maxn*2];
struct Query
{
    int v;
    int w;
    int next;
} query[maxn];
int top,top2;
int init()
{
    memset(vis,0,sizeof(vis));
    memset(point,-1,sizeof(point));
    memset(point2,-1,sizeof(point2));
    top=0;
    top2=0;
}
int add_edge(int u,int v)
{
    edge[top].v=v;
    edge[top].next=point[u];///上一条边的编号
    point[u]=top++;///u点的第一条边编号变成head
}
int findset(int x) ///并查集
{
    if(x!=pre[x])
    {
        pre[x]=findset(pre[x]); ///路径压缩
    }
    return pre[x];
}
int add_query(int u,int v)
{
    query[top2].v=v;
    query[top2].w=-1;
    query[top2].next=point2[u];///上一条边的编号
    point2[u]=top2++;///u点的第一条边编号变成head
    query[top2].v=u;
    query[top2].w=-1;
    query[top2].next=point2[v];///上一条边的编号
    point2[v]=top2++;///u点的第一条边编号变成head
}
int lca(int u,int f) ///当前节点，父节点
{
    pre[u]=u;  ///设立当前节点的集合
    for(int i=point[u]; i!=-1; i=edge[i].next)
    {
        if(edge[i].v==f)
            continue;
        lca(edge[i].v,u);  ///搜索子树
        pre[edge[i].v]=u; ///合并子树
    }
    vis[u]=1; ///以u点为集合的点搜索完毕
    for(int i=point2[u]; i!=-1; i=query[i].next)
    {
        if(vis[query[i].v]==1)
            query[i].w=findset(query[i].v);
    }
    return 0;
}
int main()
{
    int root[maxn];
    int T;
    scanf("%d",&T);
    for(int ii=0; ii<T; ii++)
    {
        init();
        int tot,r=-1,a,b;
        scanf("%d",&tot);
        for(int i=1; i<=tot; i++)
            root[i]=i;
        for(int i=0; i<tot-1; i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b);
            add_edge(b,a);
            root[b]=a;
        }
        for(int i=1; i<=tot; i++)
            if(root[i]==i)
                r=i;///树的根
        scanf("%d%d",&a,&b);
        add_query(a,b);
        lca(r,r);
        for(int i=0;i<top2;i++)
        {
            if(query[i].w!=-1)
                printf("%d\n",query[i].w);
        }
        
    }
    return 0;
}

倍增算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
using namespace std;
typedef long long LL;
const int N = 100005;

int n , m , pre[N] ,rt[N], mcnt;
bool vis[N];
struct edge
{
    int x , next;
} e[N << 1];

int dep[N] , f[17][N] , Lev , s[N];///1<<16 < N, f[j][i] 表示i的第2^j个祖先

void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = pre[x] ; ~i ; i = e[i].next)
    {
        int y = e[i].x;
        if (y != fa)
        {
            dfs(y , x);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty())
    {
        int fa = q.front();
        q.pop();
        for (int i = pre[fa] ; ~i ; i = e[i].next)
        {
            int x = e[i].x;
            if (!vis[x])
            {
                dep[x] = dep[fa] + 1;
                f[0][x] = fa ,vis[x] = 1;
                q.push(x);
            }
        }
    }
}
int LCA(int x , int y)
{
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init()
{
    memset(pre , -1 , sizeof(pre));
    memset(rt,0,sizeof(rt));
    mcnt = 0;
}
void addedge(int x,int y)
{
    e[mcnt].x = y,
    e[mcnt].next = pre[x],
    pre[x] = mcnt ++;
}
void work()
{
    int i , j , x , y , z,anc;
    init();
    scanf("%d",&n);
    for (i = 1 ; i < n ; ++ i)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        rt[y]  =x;
    }
    for(int i=1; i<=n; i++)
    {
        if(rt[i]==0)
        {
            anc = i;
            break;
        }
    }
    dfs(anc , 0);
    for (j = 1 ; 1 << j < n ; ++ j)
        for (i = 1 ; i <= n ; ++ i)
            f[j][i] = f[j - 1][f[j - 1][i]];
    Lev = j - 1;
    scanf("%d%d",&x,&y);
    if (dep[x] < dep[y])
        swap(x , y);
    printf("%d\n",LCA(x , y));
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        work();
    }
    return 0;
}