#include<stdio.h>
#include<memory.h>
#define N 1001
#define Clear(a) memset(a,0,sizeof(a))
struct Edge
{
    int v;
    Edge *link;
    Edge(int v0,Edge *e):v(v0),link(e){}
}*E[N],*Q[N];
int n,m,root;
int father[N],count[N],color[N],anc[N],d[N];

void InitData()
{
    int u,v,i,j,k;
    Clear(E);
    Clear(Q);
    Clear(d);
    Clear(count);
    Clear(color);
    for(k=1;k<=n;k++){
        scanf("%d",&u);
        while(getchar()!='(');
        scanf("%d",&i);
        while(getchar()!=')');
        for(j=1;j<=i;j++){
            scanf("%d",&v);
            d[v]++;
            E[u]=new Edge(v,E[u]);
        }
    }
    for(root=1;root<=n;root++)
        if(!d[root])
            break;
    scanf("%d",&m);
    for(j=1;j<=m;j++){
        while(getchar()!='(');
        scanf("%d%d",&u,&v);
        if(u==v)
            count[u]++;
        else{
            Q[u]=new Edge(v,Q[u]);
            Q[v]=new Edge(u,Q[v]);
        }
        while(getchar()!='(');
    }
}
int find_set(int s)
{
    for(;s!=father[s];s=father[s]);
    return s;
}
void union_set(int u,int v)
{
    int up=find_set(u);
    int vp=find_set(v);
    if(up!=vp)
        father[vp]=up;
}
void dfs(int s)
{
    father[s]=s;
    anc[s]=s;
    for(Edge *e=E[s];e;e=e->link){
        dfs(e->v);
        union_set(s,e->v);
        anc[find_set(s)]=s;
    }
    color[s]=1;
    for(Edge *e=Q[s];e;e=e->link){
        if(color[e->v])
            count[anc[find_set(e->v)]]++;
    }
}
void show()
{
    for(int i=1;i<=n;i++)
        if(count[i])
            printf("%d:%d\n",i,count[i]);
}
int main()
{  //  freopen("data.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        InitData();
        dfs(root);
        show();
    }
    return 0;
}

• 奇怪，我改成STL的就AC了，不明白邻接表怎么就出问题了 (1796) aliu0932 2009-12-05 11:24:00