2012-10-05 19:36:33Morris
[ZJ][LCA][offline] d767. 血緣關係
內容 ：
給一張祖譜,詢問 A , B 兩人關係最近的共同祖先 以及 A , B 之間的親等
example 1
親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。
※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。
example 1
親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。
※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。
輸入說明
：
第一行兩個數字 N , Q
分別代表接下來會有 N 行數字分別代表該人的兒女編號(以 0 表結束)，
再來會有 Q 行
每行上會有兩個數字 A , B ，代表要求出 A , B 兩人的關係最近的共同祖先
以及 A , B 之間的親等。
詳細請參考Sample Input。
(N≦3,0000, 1≦A,B≦N, Q≦N2)
輸出說明
：
輸出兩個數字最近的共同祖先 以及 A , B 之間的親等
範例輸入
：
7 6 2 3 0 4 5 0 6 7 0 0 0 0 0 4 5 4 2 4 4 4 3 1 7 2 3
範例輸出 ：
2 2 2 1 4 0 1 3 1 2 1 2
提示
：
背景知識：
RMQ
※ 在此未符合實際事實，暫定一個人的兒女不超過6個
Ranged Minimum/Maximum Query(RMQ)
Least Common Ancestors (LCA)
出處
：
RMQ & LCA
(管理：morris1028)
學習文章 <- 請點閱
#include <stdio.h>
#include <vector>
#define maxN 32768
using namespace std;
typedef struct {
int q, i;
} Qi;
vector<int> g[maxN];
vector<Qi> qu[maxN];
int r[maxN], p[maxN], dp[maxN], used[maxN];
int oput[500000][2];
int findp(int x) {
return p[x] == x ? x : p[x]=findp(p[x]);
}
void joint(int x, int y) {
x = findp(x), y = findp(y);
p[x] = y;
}
void dfs(int nd, int dep) {
dp[nd] = dep, used[nd] = 1;
for(vector<Qi>::iterator it = qu[nd].begin();
it != qu[nd].end(); it++) {
if(used[it->q]) {
oput[it->i][0] = findp(it->q);
oput[it->i][1] = dp[nd]+dp[it->q]-2*dp[findp(it->q)];
}
}
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
dfs(*it, dep+1);
joint(*it, nd);
}
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, q, x, y, i, j;
while(scanf("%d %d", &n, &q) == 2) {
for(i = 1; i <= n; i++) {
g[i].clear(), r[i] = 1, p[i] = i, used[i] = 0;
while(ReadInt(&x), x)
g[i].push_back(x);
}
Qi tmp;
for(i = 0; i < q; i++) {
ReadInt(&x), ReadInt(&y);
tmp.i = i, tmp.q = y;
qu[x].push_back(tmp);
tmp.q = x;
qu[y].push_back(tmp);
}
dfs(1, 0);
for(i = 0; i < q; i++)
printf("%d %d\n", oput[i][0], oput[i][1]);
}
return 0;
}
學習文章 <- 請點閱
#include <stdio.h>
#include <vector>
#define maxN 32768
using namespace std;
typedef struct {
int q, i;
} Qi;
vector<int> g[maxN];
vector<Qi> qu[maxN];
int r[maxN], p[maxN], dp[maxN], used[maxN];
int oput[500000][2];
int findp(int x) {
return p[x] == x ? x : p[x]=findp(p[x]);
}
void joint(int x, int y) {
x = findp(x), y = findp(y);
p[x] = y;
}
void dfs(int nd, int dep) {
dp[nd] = dep, used[nd] = 1;
for(vector<Qi>::iterator it = qu[nd].begin();
it != qu[nd].end(); it++) {
if(used[it->q]) {
oput[it->i][0] = findp(it->q);
oput[it->i][1] = dp[nd]+dp[it->q]-2*dp[findp(it->q)];
}
}
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
dfs(*it, dep+1);
joint(*it, nd);
}
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, q, x, y, i, j;
while(scanf("%d %d", &n, &q) == 2) {
for(i = 1; i <= n; i++) {
g[i].clear(), r[i] = 1, p[i] = i, used[i] = 0;
while(ReadInt(&x), x)
g[i].push_back(x);
}
Qi tmp;
for(i = 0; i < q; i++) {
ReadInt(&x), ReadInt(&y);
tmp.i = i, tmp.q = y;
qu[x].push_back(tmp);
tmp.q = x;
qu[y].push_back(tmp);
}
dfs(1, 0);
for(i = 0; i < q; i++)
printf("%d %d\n", oput[i][0], oput[i][1]);
}
return 0;
}