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

05-树8 File Transfer (25分)

程序员文章站 2022-03-27 16:02:21
...

05-树8 File Transfer (25分)
05-树8 File Transfer (25分)
05-树8 File Transfer (25分)
05-树8 File Transfer (25分)思路分析:本题的意思就是给出一串数字让你检查他们是否有在一个集合,因为计算机是双向连接,所以就相当于是一颗树,将他们并在一起。
值得注意的是,我们将这些树存放在数组中,数组的下标就是计算机的序号(也就是节点的值),数组的值就是他对应的父节点。首先我们要进行初始化,将每一个父节点初始化为-1,尽量少使用全局变量,所以这里typedef了一个数组类型然后记得要在主函数中初始化对象。

#include <iostream>
#define MaxSize 10001
#define Initial -1
typedef int Computer[MaxSize];
using namespace std;

void Check(Computer C);
void Input(Computer C);
void Initialize(Computer C, int n);
void Union(Computer C, int n, int m);
int Find(Computer C, int a);
void CheckNetwork(Computer C, int n);

int main()
{
    Computer C;//初始化
    int ComputerNum;
    char Instruction;
    cin >> ComputerNum;
    Initialize(C, ComputerNum);
    do{
        cin >> Instruction;
        switch(Instruction)
        {
            case 'C': Check(C);break;
            case 'I': Input(C);break;
            case 'S': CheckNetwork(C,ComputerNum); break;
        }
    }while(Instruction!='S');//do while语句有双引号
    return 0;
}
void Input(Computer C)
{
    int com1,com2;
    int root1,root2;
    cin >> com1 >> com2;
    root1 = Find(C,com1);
    root2 = Find(C,com2);
    if(root1!=root2) Union(C,root1,root2);
}
void Check(Computer C)
{
    int com1,com2;
    int root1,root2;
    cin >> com1 >> com2;
    root1 = Find(C,com1);
    root2 = Find(C,com2);
    if(root1==root2) cout<<"yes"<<endl;
    else cout <<"no"<<endl;
}
void Initialize(Computer C,int n)
{
    int i = 1;
    for(i = 1; i<=n; i++)C[i] = Initial;
}
void Union(Computer C, int n, int m)
{
    if(n<m){
        C[n] += C[m];//加起来表示总的节点个树,也可以不用加
        C[m] = n;
    }else
    {
        C[m]+=C[n];
        C[n] = m;
    }
}
int Find(Computer C, int a)//路径压缩
{
    if(C[a]<0)return a;
    else return C[a] = Find(C,C[a]);//使得每一个节点的父节点都是一个,方便查找
}
void CheckNetwork(Computer C,int n)
{
    int i = 1;
    int count = 0;
    for(i = 1; i<=n;i++)
    {
        if(C[i]<0)count++;
    }
    if(count == 1) cout<<"The network is connected."<<endl;
    else  cout<<"There are "<<count <<" components."<<endl;
}