文章

14

粉丝

230

获赞

26

访问

71.1k

头像
并查集
P1315 浙江大学机试题
发布于2022年8月30日 10:17
阅读数 4.9k

利用实现并查集的思想(通过一个数组存储关系,查的过程就是顺着链查找)

类似于树的双亲表示法,树的双亲表示法中,数组中记录的是双亲是谁

这里,亲戚关系中,双亲不是唯一的,但是孩子却是唯一的,所以可以用一个数组存储孩子是谁

查找两个人是否是直系亲戚,

就是从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;
          ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发