欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

pta 05-树8 File Transfer (25分) c语言实现

程序员文章站 2022-03-27 14:14:08
...

提交图:

不了解并查集的百度下,不过这个不是典型的并查集吧。

pta 05-树8 File Transfer (25分) c语言实现

具体代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100001
typedef struct Node
{
    int flag;  /*标记数,用来区分是否是一个集合里面的*/
    int data;
}BINCHA;
BINCHA h[MAX];
int da(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    int i,j,m,can1,can2,qw[MAX];
    int u=0;
    char st;
    scanf("%d",&m);
    for(i=0;i<m;i++)/*初始化这个集合*/
    {
        h[i].data=i+1;
        h[i].flag=-1;
    }
    j=1;
    getchar();
    while(1)/*开始输入*/
    {
        scanf("%c",&st);
        if(st-'I'==0)/*判断第一个字符*/
        {
            scanf("%d %d",&can1,&can2);
            if((h[can1-1].flag==-1)&&(h[can2-1].flag==-1))/*如果这两个数的标识数都为-1,那都没有加入任何集合,那就加入一个集合*/
            {
                h[can1-1].flag=j;
                h[can2-1].flag=j;
                j++;
            }
            else if((h[can1-1].flag!=-1)&&(h[can2-1].flag==-1))
            {
                h[can2-1].flag=h[can1-1].flag;/*有一个加入了,另一个没有,并入一起*/
            }
            else if((h[can1-1].flag==-1)&&(h[can2-1].flag!=-1))
            {
                h[can1-1].flag=h[can2-1].flag;
            }
            else/*两个都加入了集合,将两个集合合并*/
            {
                if(h[can1-1].flag==h[can2-1].flag)
                    continue;
                else
                {
                    if(h[can1-1].flag>h[can2-1].flag)/*将标识数大的加入标记数小的集合里面*/
                    {
                        int fg;
                        fg =h[can1-1].flag;
                        for(int g=0;g<m;g++)
                        {
                            if(h[g].flag==fg)
                                h[g].flag=h[can2-1].flag;
                        }
                    }
                    else
                    {
                        int fg;
                        fg =h[can2-1].flag;
                        for(int g=0;g<m;g++)
                        {
                            if(h[g].flag==fg)
                                h[g].flag=h[can1-1].flag;
                        }
                    }
                }
            }
        }
        else if(st-'C'==0)
        {
            scanf("%d %d",&can1,&can2);
            if((h[can1-1].flag==h[can2-1].flag)&&((h[can1-1].flag!=-1)&&(h[can2-1].flag!=-1)))/*判断如果两个数的标记数相等qie不为负一就是联通的,数组存放这个值*/
                qw[u++]=1;
            else
                qw[u++]=0;
        }
        else if(st-'S'==0)
            break;
        getchar();
    }
    for(i=0;i<u;i++)/*输出no和yes*/
    {
        if(qw[i]==0)
            printf("no\n");
        else
            printf("yes\n");
    }
    int r,t,v,kl,as,sum;
    as=0;
    sum=0;
    v=1;
    r=h[0].flag;
    t=0;
    kl=1;
    while(1)
    {/*从1开始向后递增,每次对比标记数,当这个值为0时,就可以break出去*/
        for(i=0;i<m;i++)
        {
            if(h[i].flag==kl)
                as++;
        }
        sum=sum+as;
        if(as==0)
            break;
        t++;/*主要来判断还剩几个集合*/
        kl++;
        as=0;
    }
    if(sum!=m)/*如果相等就说明标记数中没有-1,不相等就有,就要加上1*/
        t++;
    for(i=0;i<m;i++)
    {
        if(h[i].flag==-1)/*是否有-1*/
            v=0;
    }
    if(t==1&&v==0)/*根据t与v输出*/
        printf("There are %d components.",m);
    else if(t!=1)
        printf("There are %d components.",t);
    else
        printf("The network is connected.");
    return 0;
}

第一次写csdn,代码不足请指出,我也在学习

相关标签: pta c语言