POJ 1470 Closest Common Ancestors

acm lca

學習lca, 把倍增, Tarjon, 轉 RMQ 都寫一次

倍增

poj1470a.cpp
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
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

#define MAXN 1000
#define DEG 15

struct edge {
    int to, nxt;
} E[MAXN*1000], QRY[MAXN*1000];
int Ehead[MAXN];
int deep[MAXN], father[MAXN][DEG];
int eidx;

bool isChild[MAXN];
int result[MAXN];

void init() {
    eidx = 0;
    memset(isChild, false, sizeof(isChild));
    memset(Ehead, -1, sizeof(Ehead));
    memset(result, 0, sizeof(result));
}

void add_edge(int from, int to) {
    E[eidx].to = to;
    E[eidx].nxt = Ehead[from];
    Ehead[from] = eidx++;
}

void BFS(int root) {
    queue<int> Q;
    deep[root] = 0;
    father[root][0] = root;
    Q.push(root);

    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i = 1; i < DEG; ++i)
            father[u][i] = father[father[u][i-1]][i-1];
        for(int i = Ehead[u]; i != -1; i = E[i].nxt) {
            int v = E[i].to;
            deep[v] = deep[u] + 1;
            father[v][0] = u;
            Q.push(v);
        }
    }
}

// v is deeper
int LCA(int u, int v) {
    if(deep[u] > deep[v]) swap(u, v);
    int hv = deep[v], hu = deep[u];
    int tu = u, tv = v;
    // raise v to same deep as u
    for(int diff = hv - hu, i = 0; diff; ++i, diff>>=1)
        if(diff&1) // 5 = 101 = 2^0 + 2^2
            tv = father[tv][i];

    if(tu==tv) return tu;

    // raise both u and v and find the intersect point
    for(int i = DEG-1; i >= 0; --i) {
        if(father[tu][i] == father[tv][i]) continue;
        tu = father[tu][i];
        tv = father[tv][i];
    }
    return father[tu][0];
}


int main() {
    // freopen("input.txt", "r", stdin);
    int n, m, curNode, toNode, ntoNode;

    while(scanf("%d", &n) != EOF) {
        init();

        for(int i = 0; i < n ;++i) {
            scanf("%d:(%d)", &curNode, &ntoNode);

            for(int i2 = 0; i2 < ntoNode; ++i2) {
                scanf("%d", &toNode);
                add_edge(curNode, toNode);
                isChild[toNode] = true;
            }
        }

        for(int i = 1; i <= n; ++i)
            if(!isChild[i])
                BFS(i);

        scanf("%d\n", &m);
        for(int i = 0; i < m; ++i) {
            scanf("(%d %d) ", &curNode, &toNode);
            int lca = LCA(curNode, toNode);
            result[lca]++;
        }

        for(int i = 1; i <= n; ++i)
            if(result[i])
                printf("%d:%d\n", i, result[i]);

    }
    return 0;
}

Tarjon

poj1470b.cpp
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
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

#define MAXN 1000
#define DEG 15

struct edge {
    int to, nxt;
} E[MAXN*1000], QRY[MAXN*1000];
int Ehead[MAXN];
int QRYhead[MAXN];
int parent[MAXN];
bool visited[MAXN];
int eidx, qidx;

bool isChild[MAXN];
int result[MAXN];

void init() {
    eidx = qidx = 0;
    memset(isChild, false, sizeof(isChild));
    memset(Ehead, -1, sizeof(Ehead));
    memset(QRYhead, -1, sizeof(QRYhead));
    memset(result, 0, sizeof(result));
    memset(visited, false, sizeof(visited));
}

void add_edge(int from, int to) {
    E[eidx].to = to;
    E[eidx].nxt = Ehead[from];
    Ehead[from] = eidx++;
}

void add_query(int from, int to) {
    QRY[qidx].to = to;
    QRY[qidx].nxt = QRYhead[from];
    QRYhead[from] = qidx++;

    QRY[qidx].to = from;
    QRY[qidx].nxt = QRYhead[to];
    QRYhead[to] = qidx++;
}

int find_parent(int x) {
    if(parent[x] != x)
        parent[x] = find_parent(parent[x]);
    return parent[x];
}

void Tarjan(int u) {

    parent[u] = u;

    for(int i = Ehead[u]; i != -1; i = E[i].nxt) {
        int v = E[i].to;
        Tarjan(v);
        parent[v] = u;
    }

    visited[u] = true;

    for(int i = QRYhead[u]; i != -1; i = QRY[i].nxt) {
        int v = QRY[i].to;
        if(!visited[v]) continue;

        result[find_parent(v)]++;
    }
}


int main() {
    // freopen("input.txt", "r", stdin);
    int n, m, curNode, toNode, ntoNode;

    while(scanf("%d", &n) != EOF) {
        init();

        for(int i = 0; i < n ;++i) {
            scanf("%d:(%d)", &curNode, &ntoNode);

            for(int i2 = 0; i2 < ntoNode; ++i2) {
                scanf("%d", &toNode);
                add_edge(curNode, toNode);
                isChild[toNode] = true;
            }
        }

        scanf("%d\n", &m);
        for(int i = 0; i < m; ++i) {
            scanf("(%d %d) ", &curNode, &toNode);
            add_query(curNode, toNode);
        }

        for(int i = 1; i <= n; ++i)
            if(!isChild[i])
                Tarjan(i);

        for(int i = 1; i <= n; ++i)
            if(result[i])
                printf("%d:%d\n", i, result[i]);
    }
    return 0;
}

轉 RMQ

poj1470c.cpp
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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define MAXN 1000
#define DEG 15

struct edge {
    int to, nxt;
} E[MAXN*1000];
int Ehead[MAXN];
int result[MAXN];
int eidx;

bool isChild[MAXN];


void add_edge(int from, int to) {
    E[eidx].to = to;
    E[eidx].nxt = Ehead[from];
    Ehead[from] = eidx++;
}

int D[MAXN << 1];
int first[MAXN];
int depth[MAXN << 1];
int dp[MAXN << 1][DEG];
int idx;
void dfs(int u, int dep) {
    D[++idx] = u;
    depth[idx] = dep;
    first[u] = idx;

    for(int i = Ehead[u]; i != -1; i = E[i].nxt) {
        int to = E[i].to;
        dfs(to, dep + 1);

        D[++idx] = u;
        depth[idx] = dep;
    }
}

void RMQ_init(int N) {
    for(int i = 1; i <= N; ++i) dp[i][0] = i;

    for(int j = 1; (1 << j) <= N; ++j)
        for(int i = 1; i + (1<<j) - 1 <= N; ++i)
            dp[i][j] =  depth[dp[i][j-1]]<depth[dp[i+(1<<(j-1))][j-1]]?
                dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}

int RMQ_min(int u, int v) {
    if(v < u) swap(u, v);
    int k = log2(v - u + 1);
    return depth[dp[u][k]]<depth[dp[v-(1<<k)+1][k]]?
            dp[u][k]:dp[v-(1<<k)+1][k];
}


void init() {
    eidx = 0;
    idx = 0;
    memset(isChild, false, sizeof(isChild));
    memset(Ehead, -1, sizeof(Ehead));
    memset(result, 0, sizeof(result));
}


int main() {
    // freopen("input.txt", "r", stdin);
    int n, m, curNode, toNode, ntoNode;

    while(scanf("%d", &n) != EOF) {
        init();

        for(int i = 0; i < n ;++i) {
            scanf("%d:(%d)", &curNode, &ntoNode);

            for(int i2 = 0; i2 < ntoNode; ++i2) {
                scanf("%d", &toNode);
                add_edge(curNode, toNode);
                isChild[toNode] = true;
            }
        }

        for(int i = 1; i <= n; ++i)
            if(!isChild[i]) {
                dfs(i, 0);
                break;
            }

        RMQ_init(n*2);

        scanf("%d\n", &m);
        for(int i = 0; i < m; ++i) {
            scanf("(%d %d) ", &curNode, &toNode);
            int lca = D[RMQ_min(first[curNode], first[toNode])];
            result[lca]++;
        }

        for(int i = 1; i <= n; ++i)
            if(result[i])
                printf("%d:%d\n", i, result[i]);

    }
    return 0;
}