POJ1330 Nearest Common Ancestors

今天第一次学习（LCA）最近公共祖先算法，就做了这个题目，本题的意思就是给你一颗树，两个节点的最短路径上深度最小的节点，说白了就是LCA

如有不懂得可以点击http://www.cnblogs.com/ka200812/archive/2011/08/02/2124984.html

#include<iostream>
#include<vector>
using namespace std;
const int N=10002;
int r[N],father[N],fa[N],vis[N],in[N];
vector<int> map[N],Q[N];
int n;
void init()
{
    for(int i=1;i<=n;i++)
    {
        
        r[i]=1;//每个集合初始一个点
        father[i]=i;
        in[i]=0;//入度
        vis[i]=0;//标记数组
        fa[i]=0;//祖先
        map[i].clear();  
        Q[i].clear();
    }
}
int find(int x)
{
    if(father[x]==x)
        return x;
    else
        father[x]=find(father[x]);
    return father[x];
}
void Union(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x==y)return ;
    
    else    if(r[x]<=r[y])//小集合向大集合合并，可以节约时间这都是并查集操作
        {
            father[x]=y;
            r[y]+=r[x];
        }
        else 
        {
            father[y]=x;
            r[x]+=r[y];
        }
    
}

void lca(int u)  
{  
    fa[u]=u; 
    int i;
    int size = map[u].size();  
    for(i=0;i<size;i++)  
    {  
        lca(map[u][i]);  
        Union(u,map[u][i]);  
        fa[find(u)]=u;  
    }  
    vis[u]=1;  
    size = Q[u].size();  
    for(i=0;i<size;i++)  
    {  
        //如果已经访问了问题节点,就可以返回结果了.  
        if(vis[Q[u][i]]==1)  
        {  
            printf("%d
",fa[find(Q[u][i])]); 
            return;  
        }  
    }  
}  

int main()
{
    int t,i,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            map[x].push_back(y);
            in[y]++;
        }
        scanf("%d%d",&x,&y);
        Q[x].push_back(y);  
        Q[y].push_back(x);
        for(i=1;i<=n;i++)
        {
            if(in[i]==0)
            {
                lca(i);
                break;
            }
        }
    }
    return 0;
}

这题被坑了10次啊，一直WA，原来我并查集操作些错了，后来改了就AC。坑了我3个小时