题目
求两点的最近公共祖先
分析
由于询问次数少,于是就只打Tarjan(不是求强联通分量的)懒
代码
#include <cstdio>
using namespace std
;
struct node
{short y
,next
;}e
[20001]; int t
;
short n
,ok
,q
,p
,m
,x
,y
,ls
[10001],in
[10001],v
[10001],f
[10001];
void add(int x
,int y
){e
[++m
].y
=y
; e
[m
].next
=ls
[x
]; ls
[x
]=m
;}
int getf(int u
){return (f
[u
]==u
)?u
:getf(f
[u
]);}
void tarjan(int x
){
v
[x
]=1;
for (int i
=ls
[x
];i
;i
=e
[i
].next
){
if (v
[e
[i
].y
]) continue;
tarjan(e
[i
].y
); f
[e
[i
].y
]=x
;
}
if (ok
) return;
if (v
[q
]==2&&x
==p
){
printf("%d\n",getf(q
));
ok
=1; return;
}
if (v
[p
]==2&&x
==q
){
printf("%d\n",getf(p
));
ok
=1; return;
}
v
[x
]=2;
}
int main(){
scanf("%d",&t
);
while (t
--){
scanf("%d",&n
);
m
=ok
=0;
for (int i
=1;i
<=n
;i
++) ls
[i
]=in
[i
]=v
[i
]=0,f
[i
]=i
;
for (int i
=1;i
<n
;i
++) scanf("%d%d",&x
,&y
),in
[y
]++,add(x
,y
),add(y
,x
);
scanf("%d%d",&q
,&p
);
for (int i
=1;i
<=n
;i
++) if (!in
[i
]) tarjan(i
);
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-3350355.html