首页 > 代码库 > 【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