错误代码:
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=10010;
unordered_map<int,int>d,res,order,fa;
int pre[N],in[N];
unordered_map<int,int>l,r,p;
//int idx;
/*void build(int &root,int x){
if(root==0){
root=++idx;
p[root]=x;
}
else{
if(x<p[root]){
build(l[root],x);
}
else{
build(r[root],x);
}
}
}*/
int build(int il,int ir,int pl,int pr,int depth){
int root=pre[pl];
int index=order[root];
if(il<index){
l[root]=build(il,index-1,pl+1,pl+index-il,depth+1);
}
if(index<ir){
r[root]=build(index+1,ir,pl+index-il+1,pr,depth+1);
}
return root;
}
void dfs(int x,int depth){
if(!x)
return ;
d[x]=depth;
fa[l[x]]=x;
dfs(l[x],depth+1);
fa[r[x]]=x;
dfs(r[x],depth+1);
}
int main(){
int m,n;
cin>>m>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
res[x]++;
// build(root,x);
pre[i]=x;
in[i]=x;
}
sort(in,in+n);
for(int i=0;i<n;i++){
order[in[i]]=i;
}
int root=build(0,n-1,0,n-1,0);
dfs(root,0);
int mi=m-1;
while(m--){
if(mi!=m){
printf("\n");
}
int l,r;
cin>>l>>r;
if(res.count(l)&&res.count(r)){
int a=l,b=r;
while(l!=r){
if(d[l]<d[r]){
r=fa[r];
}
else{
l=fa[l];
}
}
if(l!=a&&r!=b){
printf("LCA of %d and %d is %d.",a,b,l);
}
else if(l==a){
printf("%d is an ancestor of %d.",a,b);
}
else{
printf("%d is an ancestor of %d.",b,a);
}
}
else{
if(!res.count(l)&&!res.count(r)){
printf("ERROR: %d and %d are not found.",l,r);
}
else if(!res.count(l)){
printf("ERROR: %d is not found.",l);
}
else{
printf("ERROR: %d is not found.",r);
}
}
}
return 0;
}
正确代码1:
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=10010;
unordered_map<int,int>res;
int in[N],pre[N],d[N],seq[N],p[N],l[N],r[N];//-----------》映射,数组内查找比哈希表内查找时间不同
//---------------》根据本题目的时间和复杂度,必须进行离散化!!
int build(int il,int ir,int pl,int pr,int depth){
int root=pre[pl];
int index=root;
d[root]=depth;
if(il<index){
l[root]=build(il,index-1,pl+1,pl+index-il,depth+1);
}
if(index<ir){
r[root]=build(index+1,ir,pl+index-il+1,pr,depth+1);
}
return root;
}
void dfs(int u){
if(!u)
return ;
p[l[u]]=u;
dfs(l[u]);
p[r[u]]=u;
dfs(r[u]);
}
int main(){
int m,n;
cin>>m>>n;
int x;
for(int i=1;i<=n;i++){
scanf("%d",&x);
seq[i]=x;
pre[i]=x;
}
sort(seq+1,seq+n+1);
for(int i=1;i<=n;i++){
in[i]=i;
res[seq[i]]=i;
}
for(int i=1;i<=n;i++)
{
pre[i]=res[pre[i]];
}
int root=build(1,n,1,n,0);
dfs(root);
int mi=m-1;
while(m--){
if(mi!=m){
printf("\n");
}
int l,r;
scanf("%d%d",&l,&r);
if(res.count(l)&&res.count(r)){
int a=res[l],b=res[r];
int x=a,y=b;
while(a!=b){
if(d[a]<d[b]){
b=p[b];
}
else{
a=p[a];
}
}
if(x!=a&&y!=b){
printf("LCA of %d and %d is %d.",l,r,seq[a]);
}
else if(x==a){
printf("%d is an ancestor of %d.",l,r);
}
else{
printf("%d is an ancestor of %d.",r,l);
}
}
else{
if(!res.count(l)&&!res.count(r)){
printf("ERROR: %d and %d are not found.",l,r);
}
else if(!res.count(l)){
printf("ERROR: %d is not found.",l);
}
else{
printf("ERROR: %d is not found.",r);
}
}
}
return 0;
}
正确代码2:
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=10010;
unordered_map<int,int>res;
int in[N],pre[N],d[N],seq[N],p[N];
int build(int il,int ir,int pl,int pr,int depth){
int root=pre[pl];
int index=root;
d[root]=depth;
if(il<index){
p[build(il,index-1,pl+1,pl+index-il,depth+1)]=root;
}
if(index<ir){
p[build(index+1,ir,pl+index-il+1,pr,depth+1)]=root;
}
return root;
}
int main(){
int m,n;
cin>>m>>n;
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
seq[i]=x;
pre[i]=x;
}
sort(seq,seq+n);
for(int i=0;i<n;i++){
in[i]=i;
res[seq[i]]=i;
}
for(int i=0;i<n;i++)
{
pre[i]=res[pre[i]];
}
build(0,n-1,0,n-1,0);
int mi=m-1;
while(m--){
if(mi!=m){
printf("\n");
}
int l,r;
scanf("%d%d",&l,&r);
if(res.count(l)&&res.count(r)){
int a=res[l],b=res[r];
int x=a,y=b;
while(a!=b){
if(d[a]<d[b]){
b=p[b];
}
else{
a=p[a];
}
}
if(x!=a&&y!=b){
printf("LCA of %d and %d is %d.",l,r,seq[a]);
}
else if(x==a){
printf("%d is an ancestor of %d.",l,r);
}
else{
printf("%d is an ancestor of %d.",r,l);
}
}
else{
if(!res.count(l)&&!res.count(r)){
printf("ERROR: %d and %d are not found.",l,r);
}
else if(!res.count(l)){
printf("ERROR: %d is not found.",l);
}
else{
printf("ERROR: %d is not found.",r);
}
}
}
return 0;
}