```c
#include<stdio.h>
struct qinqi
{
int me;
struct qinqi *p[20000];
int sum;
};
int main()
{
int n,m,Q,a,b,t;
scanf("%d%d",&n,&m);
struct qinqi q[n];
int i,j,k,h;
for(i=0;i<n;i++)
{
q[i].sum=0;
q[i].me=i;
}
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
a--;b--;
for(j=0;j<q[a].sum;j++)
if(q[a].p[j]->me==b)//a的亲戚里找b
break;
if(j==q[a].sum)
{
t=q[a].sum;
for(k=0;k<q[a].sum;k++)
{
q[a].p[k]->p[ q[a].p[k]->sum ]=&q[b];//a的k亲戚加上b并且把b的亲戚加上;
q[a].p[k]->sum++;
for(h=0;h<q[b].sum;h++)
{
q[a].p[k]->p[ q[a].p[k]->sum ]=q[b].p[h];
q[a].p[k]->sum++;
}
}
q[a].p[ q[a].sum ]=&q[b];//a加上b并且把b的亲戚加上;
q[a].sum++;
for(h=0;h<q[b].sum;h++)
{
q[a].p[ q[a].sum ]=q[b].p[h];
q[a].sum++;
}
// ************************************************
// ************************************************
for(k=0;k<q[b].sum;k++)
{
q[b].p[k]->p[ q[b].p[k]->sum ]=&q[a];//b的k亲戚加上a并且把a的亲戚加上;
q[b].p[k]->sum++;
for(h=0;h<t;h++)
{
q[b].p[k]->p[ q[b].p[k]->sum ]=q[a].p[h];
q[b].p[k]->sum++;
}
}
q[b].p[ q[b].sum ]=&q[a];//b加上a并且把a的亲戚加上;
q[b].sum++;
for(h=0;h<t;h++)
{
q[b].p[ q[b].sum ]=q[a].p[h];
q[b].sum++;
}
}
}
scanf("%d",&Q);
for(i=0;i<Q;i++)
{
scanf("%d%d",&a,&b);
a--;b--;
for(j=0;j<q[a].sum;j++)
if(q[a].p[j]->me==b)//a的亲戚里找b
{
printf("Yes\n");
break;
}
if(j==q[a].sum)
printf("No\n");
}
}//自己写的自己看了都头晕【捂脸】.就是Devc++上运行得出,oj运行错误57%,求大佬救救,辛苦辛苦。下面是数组的
/*
#include<stdio.h>
int main()
{
int m,n;
scanf("%d%d",&n,&m);
int q[n+1][n+1];
int i,j,k,h;
for(i=1;i<=n;i++)
q[i][0]=1;
int a,b,Q,t;
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
for(j=1;j<q[a][0];j++)
if(q[a][j]==b)//a的亲戚里找b
break;
if(j==q[a][0])
{
t=q[a][0];//a本来亲戚的数目
for(k=1;k<q[a][0];k++)
{
q[ q[a][k] ][ q[ q[a][k] ][0] ]=b;//a的k亲戚加上b;
q[ q[a][k] ][0]++;
for(h=1;h<q[b][0];h++)
{
q[ q[a][k] ][ q[ q[a][k] ][0] ]=q[b][h];//并且把b的亲戚加上;
q[ q[a][k] ][0]++;
}
}
q[a][ q[a][0] ]=b;//a加上b;
q[a][0]++;
for(h=1;h<q[b][0];h++)
{
q[a][ q[a][0] ]=q[b][h];//并且把b的亲戚加上;
q[a][0]++;
}
// ************************************************
// ************************************************
for(k=1;k<q[b][0];k++)
{
q[ q[b][k] ][ q[ q[b][k] ][0] ]=a;//b的k亲戚加上a;
q[ q[b][k] ][0]++;
for(h=1;h<t;h++)
{
q[ q[b][k] ][ q[ q[b][k] ][0] ]=q[a][h];//并且把a的亲戚加上;
q[ q[b][k] ][0]++;
}
}
q[b][ q[b][0] ]=b;//b加上a;
q[b][0]++;
for(h=1;h<t;h++)
{
q[b][ q[b][0] ]=q[a][h];//并且把a的亲戚加上;
q[b][0]++;
}
}
}
scanf("%d",&Q);
for(i=0;i<Q;i++)
{
scanf("%d%d",&a,&b);
for(j=1;j<q[a][0];j++)
if(q[a][j]==b)//a的亲戚里找b
{
printf("Yes\n");
break;
}
if(j==q[a][0])
printf("No\n");
}
}
*/
```
[ New Thread ]
Problem 4238 >> 亲戚 |
202103010238 @ 2022-08-08 16:53:30
|
202003020118 @ 2022-08-17 20:46:15
注意题目输入范围,二维数组开不了这么大。本题是经典并查集模板题,可以先学习并查集算法。
|