文章
14
粉丝
230
获赞
26
访问
70.4k
利用实现并查集的思想(通过一个数组存储关系,查的过程就是顺着链查找)
类似于树的双亲表示法,树的双亲表示法中,数组中记录的是双亲是谁
这里,亲戚关系中,双亲不是唯一的,但是孩子却是唯一的,所以可以用一个数组存储孩子是谁
查找两个人是否是直系亲戚,
就是从A顺着链查找B,如果能找到,就是有关系,flag=1 A是B的长辈
然后从B顺着链查找A,如果能找到,就是有关系,flag=0 B是A的长辈
否则就是没有关系 (通过flag的值,确定是parent child)
用一个变量step,表示查找次数,查找一次,就是父母或者孩子,查找两次,,,,依次类推
#include<bits/stdc++.h>
using namespace std;
int a[27];
int main()
{
int m,n;
char str[4],str1[3];
while(cin>>m>>n)
{
for(int i=1; i<=m; i++)
{
scanf("%s",str);
for(int j=1; j<3; j++)
{
if(str[j]!='-')
{
a[str[j]-'A'+1]=str[0]-'A'+1;
}
}
}
for(int i=1; i<=n; i++)
{
scanf("%s",str1);
int b1 = str1[0]-'A'+1;
int b2 = str1[1]-'A'+1;
// cout<<b1<<b2<<endl;
int step=0;
...
登录后发布评论
暂无评论,来抢沙发