首页 > 代码库 > 【Poj 1330】Nearest Common Ancestors
【Poj 1330】Nearest Common Ancestors
http://poj.org/problem?id=1330
题目意思就是T组树求两点LCA.
这个可以离线DFS(Tarjan)-----具体参考
O(Tn) 0ms
还有其他在线O(Tnlogn)也可参考LCA
// This file is made by YJinpeng,created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define IN inline #define RG register using namespace std;typedef long long LL;const int N=10010;const int M=10010;inline int gi() { register int w=0,q=0;register char ch=getchar(); while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar(); if(ch==‘-‘)q=1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar(); return q?-w:w;}int t;int to[M],ne[M];int fr[N],f[N],d[N],g[N];IN void link(RG int u,RG int v){ to[++t]=v;ne[t]=fr[u];fr[u]=t;}IN int find(int x){return f[x]==x?x:f[x]=find(f[x]);}IN bool dfs(RG int x){ f[x]=x;d[x]=1; for(int o=fr[x];o;o=ne[o]){ if(dfs(to[o]))return 1; f[to[o]]=x; if(g[to[o]]&&d[g[to[o]]]){ g[to[o]]=g[g[to[o]]]=find(g[to[o]]); return true; } }return 0;}int main(){ freopen("1330.in","r",stdin); freopen("1330.out","w",stdout); int T=gi(); while(T--){ int n=gi(),m=n-1;t=0; memset(fr,0,sizeof(fr)); memset(d,0,sizeof(d)); while(m--){ int u=gi(),v=gi(); n=max(max(u,v),n);d[v]++; link(u,v); }int x=gi(),y=gi(); g[x]=y,g[y]=x; for(int i=1;i<=n;i++) if(!d[i]){ memset(d,0,sizeof(d)); dfs(i);break; } printf("%d\n",g[x]);g[x]=g[y]=0; } return 0;}
【Poj 1330】Nearest Common Ancestors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。