luogu 3379最近の共通祖先(LCA)tarjan倍増
8151 ワード
読み込み最適化OJを楽しませる!
tarjanはあまり言わない
倍増も多くは言わない
tarjanはあまり言わない
#include
#include
using namespace std;
struct Edge{
int too, nxt;
}edge[1000005];
struct Ques{
int nxt, too, ran;
}ques[1000005];
int getint(){
char ch=getchar();
int re=0;
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
re = re*10 + ch - '0';
ch = getchar();
}
return re;
}
int n, m, ecnt, qcnt, ehea[500005], qhea[500005], fa[500005], uu, vv;
int s, ans[500005];
bool vis[500005];
void add_edge(int fro, int too){
edge[++ecnt].nxt = ehea[fro];
edge[ecnt].too = too;
ehea[fro] = ecnt;
}
void add_ques(int fro, int too, int ran){
ques[++qcnt].nxt = qhea[fro];
ques[qcnt].too = too;
ques[qcnt].ran = ran;
qhea[fro] = qcnt;
}
int myfind(int x){
return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
void tarjan(int u){
vis[u] = true;
for(int i=ehea[u]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t]){
tarjan(t);
fa[t] = u;
}
}
for(int i=qhea[u]; i; i=ques[i].nxt){
int t=ques[i].too;
if(vis[t])
ans[ques[i].ran] = myfind(t);
}
}
int main(){
n = getint();
m = getint();
s = getint();
for(int i=1; ifor(int i=1; i<=m; i++){
uu = getint();
vv = getint();
add_ques(uu, vv, i);
add_ques(vv, uu, i);
}
tarjan(s);
for(int i=1; i<=m; i++)
printf("%d
", ans[i]);
return 0;
}
倍増も多くは言わない
#include
#include
using namespace std;
int n, m, s, grand[500005][22], deep[500005], hea[500005], cnt, uu, vv;
struct Edge{
int too, nxt;
}edge[1000005];
int getint(){
char ch=getchar();
int re=0;
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
re = re*10 + ch - '0';
ch = getchar();
}
return re;
}
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
void builddepth(int u){
for(int i=hea[u]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!deep[t]){
deep[t] = deep[u] + 1;
grand[t][0] = u;
builddepth(t);
}
}
}
void init(){
deep[s] = 1;
builddepth(s);
for(int i=1; i<=19; i++)
for(int j=1; j<=n; j++)
grand[j][i] = grand[grand[j][i-1]][i-1];
}
int getlca(int x, int y){
if(deep[x]for(int i=19; i>=0; i--)
if(deep[grand[x][i]]>=deep[y])
x = grand[x][i];
if(x==y) return x;
for(int i=19; i>=0; i--)
if(grand[x][i]!=grand[y][i]){
x = grand[x][i];
y = grand[y][i];
}
return grand[x][0];
}
int main(){
n = getint();
m = getint();
s = getint();
for(int i=1; ifor(int i=1; i<=m; i++){
uu = getint();
vv = getint();
printf("%d
", getlca(uu, vv));
}
return 0;
}