锐客网

  1. 首页 > it技术 > >

luogu3379 最近公共祖先（LCA） tarjan 倍增

读入优化使OJ快乐！ 【luogu3379 最近公共祖先（LCA） 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; i

倍增亦不多言
#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]=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; i

    推荐阅读


    上一篇：打印int数组

    下一篇：孙子兵法～笔记与感悟9