部落：此代码部分正确

Question

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
int p[10000],k[10000],f[10001],tep[10001];
void init(int n);
int getFriend(int v);
void merge(int a, int b);
int greater(const void *a,const void *b){
int *pa,*pb;
pa = (int *)a;
pb = (int *)b;
return *pa - *pb;
}
int max=0;
int main()
{
int n,q,x,y;
int sum=0;
scanf("%d",&n);
init(10001);
for(int i=0;i<n;i++)
{
scanf("%d",&k[i]);
for(int j=0;j<k[i];j++)
{
scanf("%d",&p[j]);
if(p[j]>max)
max=p[j];
}
for(int x=0;x<k[i]-1;x++)
{
for(int y=x+1;y<k[i];y++)
{
merge(p[x],p[y]);
}
}
}
memcpy(tep,f,sizeof(f));
qsort(tep,max+1,sizeof(int),greater);
for(int i=1;i<=max;i++)
{
sum++;
while(tep[i+1]==tep[i]&&i+1<=max)
i++;
}
printf("%d %d\n",max,sum);
scanf("%d",&q);
for(int i=0;i<q;i++)
{
scanf("%d %d",&x,&y);
if(getFriend(x)==getFriend(y))
printf("Y\n");
else
printf("N\n");
}
}
void init(int n)
{
for(int i=0;i<=n;i++)
{
f[i]=i;
}
}
int getFriend(int v)
{
if(f[v]==v)
{
return v;
}
return f[v]=getFriend(f[v]);
}
void merge(int a, int b)
{
int t1=getFriend(a);
int t2=getFriend(b);
if(t1!=t2)
{
f[t2]=t1;
}
}

Answer 1

修改处见注释，供参考：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int p[10000], k, f[10002];  // k[10000], f[10001], tep[10001]; 修改
void  init(int n);
int   getFriend(int v);
void  merge(int a, int b);
//int greater(const void* a, const void* b) {
//    int* pa, * pb;
//    pa = (int*)a;
//    pb = (int*)b;
//    return *pa - *pb;
//}
int max = 0;
int main()
{
    int n, q, x, y;
    int sum = 0;
    init(10001); //修改
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &k);
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &p[j]);
            if (p[j] > max)
                max = p[j];
        }
        //for (int x = 0; x < k[i] - 1; x++)
        //{
        for (int y = 1; y < k; y++)
        {
            merge(p[0], p[y]);
        }
        //}
    }
       //memcpy(tep, f, sizeof(f));
       //qsort(tep, max + 1, sizeof(int), greater);
    for (int i = 1; i <= max; i++)
    {
        if (f[i] == i) sum++;
        //while (tep[i + 1] == tep[i] && i + 1 <= max)
        //    i++;
    }
    printf("%d %d\n", max, sum);
    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        scanf("%d %d", &x, &y);
        if (getFriend(x) == getFriend(y))
            printf("Y\n");
        else
            printf("N\n");
    }
}
void init(int n)
{
    for (int i = 1; i <= n; i++) //for (int i = 0; i <= n; i++)
    {                            //修改
        f[i] = i;
    }
}
int getFriend(int v)
{
    if (f[v] == v)
    {
        return v;
    }
    else{
        f[v] = getFriend(f[v]); //修改
        return f[v];
    }
}
void merge(int a, int b)
{
    int t1 = getFriend(a);
    int t2 = getFriend(b);
    if (t1 != t2)
    {
        f[t2] = t1;
    }
}