检查网络之并查集代码,C代码库,德仔网

代码语言

代码分类

【C】检查网络之并查集

作者:举一反三 / 发布于2012/4/7/ 653

给定一个计算机网络以及机器间的双向连线列表，每一条允许两端的计算机进行直接的我呢就传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。现要求判断任意指定两台计算机之间是否可以进行文件传输。【输入要求】第一行包含一个整数N（N≤10000），即网络中计算机的总台数，每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或C C1 C2或S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为０时，表示全部测试结束，不要对该数据做任何处理。【输出要求】（1）对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。（2）当读到S时，检查整个网络。若网络中任意两台机器间都可以传输文件，则是在一行中输出“The network is connected”，否则输出“There are k components。”,其中k是网络中连通集的个数。当N为０时，表示全部测试结束，不要对该数据做任何处理。【输出要求】（1）对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。（2）当读到S时，检查整个网络。若网络中任意两台机器间都可以传输文件，则是在一行中输出“The network is connected”，否则输出“There are k components。”,其中k是网络中连通集的个数。

#include <iostream>
using namespace std;</div>
<div>typedef struct LNode
{
int num;//记录连通子集的个数
struct LNode* head;
struct LNode* tail;
struct LNode* next;
}LNode,*LinkList;</div>
<div>LNode L[101];</div>
<div>void InitLNode(int n)//初始化各个子集
{
for(int i=1;i<=n;i++)
{
L[i].num=n; //初始化连通子集个数为n
L[i].head=&L[i];
L[i].tail=&L[i];
L[i].next=NULL;
}
}
<div>LinkList FindSetNum(int n)//求代表元,以各个集合的第一个元素为代表元并返回其地址
{
 return L[n].head;
}
<div>void SetUnion(int a,int b,int s)//合并各个子集
{
LinkList p;
p=L[a].head;
L[a].tail->next=L[b].head; //把b所在的集合的首元素与尾元素的地址分别赋给a所在的尾元素和首元素
L[a].head->tail=L[b].tail;
p=L[b].head;
while(p->next!=NULL) //把b所在集合元素的头指针指向合并之后所在的代表元
{
 p->head=L[a].head;
 p=p->next;
}
if(p->next==NULL)
p->head=L[a].head;
for(int i=1;i<=s;i++)
 L[i].num-=1;
}
<div>bool JudgeRelation(int a,int b)//判断两台电脑之间是否连接
{
if(FindSetNum(a)==FindSetNum(b))
return true;
else
return false;
}
<div>void main()
{
int s,n,a;
char m;
 while(cin>>s && s!=0)
{
InitLNode(s);
while(s==1)
{
cout<<"The network is "<<s<<" components.\n";
break;
}
while(cin>>m && (m=='C' || m=='I' || m=='S' || m=='c' || m=='s' || m=='i')) 
{
switch(m)
{
case 'C':
 case 'c':
cin>>n>>a;
if(JudgeRelation(n,a))
{
 cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
break;
case 'I':
case 'i':
cin>>n>>a;
if(!JudgeRelation(n,a))
SetUnion(n,a,s);
break;
}
if(m=='S' || m=='s')
{
 if(L[1].num==1)
{
 cout<<"The network is connected.\n";
}
else
{
cout<<"The network is "<<L[1].num<<" components.\n";
}
break;
}
}
}
}

试试其它关键字

　检查网络之　

同语言下

可能有用的

举一反三贡献的其它代码(1)

.检查网络之并查集