POJ 1470 zz

http://blog.csdn.net/apachecq/archive/2009/01/13/3769689.aspx

比较简单的LCA。我先用的是邻接表来存放树结构和查询，结果要超时。但程序应该可以在ZOJ上AC。我自己判断超时的原因可能是对于本题的多组数据输入格式，每做完一组数据后，需要对各个数据结构清0，对于动态申请的邻接表结点要逐一释放空间。这些操作对于一组输入数据可能花不了多长时间，但对于多组数据，就会花很长时间。

然后我计算了一下空间限制，对于N=900的上限，开两个二维数组来存放树和查询，采用“假指针”方式存放，空间大约占用6M左右，完全过得了空间限制。于是就改了。再次提交，AC。空间：6816K， 时间：672 MS



版本1：邻接表方式。

#include <iostream>
using namespace std;
const int MAXN = 910;
int fa[MAXN], rank[MAXN], ancestor[MAXN], ans[MAXN];
bool visit[MAXN], rt[MAXN];
struct node {
    int v;
    node *next;
};

node *tree[MAXN], *query[MAXN];
void Make_Set(int x)
{
    fa[x] = x;
    rank[x] = 0;
}
int Find_Set(int x)
{
   if (fa[x]!=x)
     fa[x] = Find_Set(fa[x]);
   return fa[x];
}
void Union_Set(int x, int y)
{
    int xRoot, yRoot;
    xRoot = Find_Set(x);
    yRoot = Find_Set(y);
    if (rank[xRoot] > rank[yRoot])
      fa[yRoot] = xRoot;
    else if (rank[yRoot] > rank[xRoot])
      fa[xRoot] = yRoot;
    else if (xRoot != yRoot)
    {
        fa[yRoot] = xRoot;
        rank[xRoot]++;
    }
}
void Tarjan(int u)
{
    node *p;

    Make_Set(u);
    ancestor[u] = u;

    for (p = tree[u]; p ; p=p->next)
    {
        Tarjan(p->v);
        Union_Set(u, p->v);
        ancestor[Find_Set(u)] = u;
    }
    visit[u] = true;
    for (p = query[u]; p ; p=p->next)
      if (visit[p->v])
        ans[ancestor[Find_Set(p->v)]]++;

}

int main()
{
    int n, n1, m,a, b, root, i, j;
    char c1, c2, c3;
    node *p, *q;
    while(scanf("%d", &n)!=EOF)
    {
        memset(rt, true, sizeof(rt));
        memset(visit, false, sizeof(visit));
        memset(ans, 0, sizeof(visit));
        memset(tree, 0, sizeof(tree));
        memset(query, 0, sizeof(query));
        for (i=1; i<=n; i++)
        {
            scanf("%d%c%c%d%c", &m, &c1, &c2, &n1, &c3);
            if (n1 > 0)
                for (j=1; j<=n1; j++)
                {
                    scanf("%d", &a);
                    rt[a] = false;
                    p = new node;
                    p->v = a;
                    p->next = tree[m];
                    tree[m] = p;
                }
        }
        for (i=1; i<=n; i++)
            if (rt[i])
            {
                root = i;
                break;
            }
        scanf("%d\n", &n1);
        for (i=1; i<=n1;i++)
        {
            while (getchar()!='(') ;

            scanf("%d %d)%c", &a, &b, &c3);
            p = new node;
            p->v = b;
            p->next= query[a];
            query[a] = p;

            p = new node;
            p->v = a;
            p->next = query[b];
            query[b] = p;
        }
        Tarjan(root);
        for (i=1; i<=n; i++)
          if (ans[i] > 0)
            printf("%d:%d\n", i, ans[i]);
        for (i=1; i<=n; i++)
        {
            p=tree[i];
            while (p!=NULL)
            {
                q = p;
                p = p->next;
                delete q;
            }
            p=query[i];
            while (p!=NULL)
            {
                q = p;
                p = p->next;
                delete q;
            }
        }


    }

    return 0;
}

版本2：二维数组

#include <iostream>
using namespace std;
const int MAXN = 910;
int fa[MAXN], rank[MAXN], ancestor[MAXN], ans[MAXN];
bool visit[MAXN], rt[MAXN];
int tree[MAXN][MAXN], query[MAXN][MAXN];
void Make_Set(int x)
{
    fa[x] = x;
    rank[x] = 0;
}
int Find_Set(int x)
{
   if (fa[x]!=x)
     fa[x] = Find_Set(fa[x]);
   return fa[x];
}
void Union_Set(int x, int y)
{
    int xRoot, yRoot;
    xRoot = Find_Set(x);
    yRoot = Find_Set(y);
    if (rank[xRoot] > rank[yRoot])
      fa[yRoot] = xRoot;
    else if (rank[yRoot] > rank[xRoot])
      fa[xRoot] = yRoot;
    else if (xRoot != yRoot)
    {
        fa[yRoot] = xRoot;
        rank[xRoot]++;
    }
}
void Tarjan(int u)
{
    int i;

    Make_Set(u);
    ancestor[u] = u;

    for (i = 1; i<=tree[u][0]; i++)
    {
        Tarjan(tree[u][i]);
        Union_Set(u, tree[u][i]);
        ancestor[Find_Set(u)] = u;
    }
    visit[u] = true;
    for (i=1; i<=query[u][0]; i++)
      if (visit[query[u][i]])
        ans[ancestor[Find_Set(query[u][i])]]++;

}

int main()
{
    int n, n1, m,a, b, root, i, j;
    char c1, c2, c3;
    while(scanf("%d", &n)!=EOF)
    {
        memset(rt, true, sizeof(rt));
        memset(visit, false, sizeof(visit));
        memset(ans, 0, sizeof(visit));
        for (i=1; i<=n; i++)
        {
            tree[i][0] = 0;
            query[i][0] = 0;
        }

        for (i=1; i<=n; i++)
        {
            scanf("%d%c%c%d%c", &m, &c1, &c2, &n1, &c3);
            if (n1 > 0)
                for (j=1; j<=n1; j++)
                {
                    scanf("%d", &a);
                    rt[a] = false;
                    tree[m][0]++;
                    tree[m][tree[m][0]] = a;
                }
        }
        for (i=1; i<=n; i++)
            if (rt[i])
            {
                root = i;
                break;
            }
        scanf("%d\n", &n1);
        for (i=1; i<=n1;i++)
        {
            while (getchar()!='(') ;

            scanf("%d %d)%c", &a, &b, &c3);
            query[a][0]++;
            query[a][query[a][0]] = b;

            query[b][0]++;
            query[b][query[b][0]] = a;

        }
        Tarjan(root);
        for (i=1; i<=n; i++)
          if (ans[i] > 0)
            printf("%d:%d\n", i, ans[i]);
    }

    return 0;
}