Closest Common Ancestors -LCA模板

E - Closest Common Ancestors

#include<stdio.h>
#include<string.h>
#include<vector>
#define M 1007
using namespace std;
int g[M][M],in[M],pre[M],cnt[M];
bool vis[M];
vector<int>v[M];
int n,m;
void init()
{
    memset(g,0,sizeof(g));
    memset(in,0,sizeof(in));
    memset(cnt,0,sizeof(cnt));
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        v[i].clear();
        pre[i]=i;
    }
}
int fond(int x)
{
    return x==pre[x]?x:pre[x]=fond(pre[x]);
}
void unin(int x,int y)
{
    int xx=fond(x);
    int yy=fond(y);
    pre[xx]=yy;
}
void dfs(int x)
{
    int len=v[x].size();
    for(int i=0; i<len; i++)
    {
        dfs(v[x][i]);
        unin(v[x][i],x);
    }
    vis[x] = true;
    for(int i=1; i<=n; i++)
        if(vis[i]&&g[x][i])
            cnt[fond(i)]+=g[x][i];
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        int a,b,c,root;
        for(int i=1; i<=n; i++)
        {
            scanf("%d:(%d)",&a,&b);
            while(b--)
            {
                scanf(" %d",&c);
                v[a].push_back(c);
                in[c]++;
            }
        }
        scanf(" %d",&m);
        while(m--)
        {
            scanf(" (%d %d)",&a,&b);
            g[a][b]++;
            g[b][a]++;
        }
        for(int i=1; i<=n; i++)
            if(!in[i])
            {
                root=i;
                break;
            }
        dfs(root);
        for(int i=1; i<=n; i++)
        {
            if(cnt[i])
                printf("%d:%d\n",i,cnt[i]);
        }
    }
    return 0;
}