首页 > 代码库 > 数据结构_课程设计——并查集:检查网络

数据结构_课程设计——并查集:检查网络

***************************************转载请注明出处:http://blog.csdn.net/lttree********************************************




这两天做数据结构课程设计,因为以前做过ACM题,感觉还可以,不是很难呀


~~~~并查集:检查网络~~~~

题目要求:

给定一个计算机网络以及机器间的双向连线列表,每一条连线允许两端的计算机进行直接的文件传输,其他计算机间若存在一条连通路径,也可以进行间接的文件传输。请写程序判断:任意指定两台计算机,它们之间是否可以进行文件传输。

输入要求:

输入由若干测试数据组成。对于每一组测试,第一行包含一个整数N(N≤10000),即网络中计算机的总台数,因而每台计算机可用1到N之间的一个正整数表示。接下来几行输入格式为 I C1 C2 或者 C C1 C2 或者 S,其中C1,C2是两台计算机的序号,I表示在C1和C2间输入一条连线,C表示检查C1和C2间是否可以传输文件,S表示该组测试数据结束。

当N为0时,表示全部测试结束,不要对该数据进行任何处理。

输出要求:

对每一组C开头的测试,检查C1与C2间是否可以传输文件,若可以,则在一行中输出“yes”,否则输出“no”。

当读到S时,检查整个网络。若网络中任意两台计算机间都可以传输文件,则在一行中输出“The network is connected.”,否则输出“There are k components.”,其中k代表网络中联通集的个数。

两组测试数据间请输出一空行分隔。

输入样例:

3

C 1 2

I 1 2

C 1 2

S

3

I 3 1

I 2 3

C 1 2

S

0

输出样例:

no

yes

There are 2 components.


yes

The network is connected.


这道题,恩。。。典型的并查集,不需要多说,并查集那一堆垒上去,就能解出来了。

垒啥?

  当然是:——初始化  ——查找函数  ——合并函数 

我这里有两种方法,一种直接数组,序号正好可以代表机器号,一个数组就解决了。

再就是用结构体,每个结构体存父节点和一个秩,秩用来合并集合时,使树高最小。


第一种,数组:

/******************************************* 
******************************************** 
*           Author:Tree                    * 
*    From :  blog.csdn.net/lttree          * 
*      Title : 并查集:检查网络            * 
*    Source: 数据结构_课程设计             * 
*      Hint :  并查集                      * 
******************************************** 
*******************************************/ 

#include <iostream>
using namespace std;

#define MAX 10000
int par[MAX+2];
// 初始化函数
void init( int n )
{
	int i;
	for( i=1;i<=n;++i )
		par[i]=i;
}
// 查找函数
int find( int x )
{
	if( x==par[x] )
		return x;
	else
		return ( find(par[x]) );
}
// 合并函数
void combine( int x,int y )
{
	int i,j;
	i=find(x);
	j=find(y);
	par[j]=i;
}

void main()
{
	// num 为机器总数,mac1,mac2为被操作的机器号,order为接受的命令
	int num,mac1,mac2;
	char order;

	while( cin>>num )
	{
		// 根据要求,如果机器总数为0,退出
		if( !num )	break;

		// ###边界处理
		if(	num<1 || num>MAX )
		{
			printf("数据越界,请重新输入!\n");
			continue;
		}
		// 初始化节点。
		init(num);

		// 循环获取命令
		while( scanf("%c",&order) )
		{
			if( order!='S' && order!='C' && order!='I' )
			{
				cout<<"命令错误,请重新输入!"<<endl;
				continue;
			}
			// 命令为 S,判断集合个数,并退出循环
			if( order=='S' )
			{
				// 集合个数查询
				int i,k=0;
				for( i=1;i<=num;++i )
					if( par[i]==i )
						++k;
				if( k==1 )	cout<<"The network is connected."<<endl;
				else	cout<<"There are %d components."<<endl;
				cout<<endl;
				break;
			}
			// 命令不为S,获取被操作两个机器号
			scanf("%d%d",&mac1,&mac2);
	
			// 命令为C,判断两个机器是否已经连接,否则命令为I,即连接两个机器
			if( order=='C' )
			{
				// 两电脑是否同集合?
				int x,y;
				x=find(mac1);
				y=find(mac2);

				if( x==y )	cout<<"yes"<<endl;
				else	cout<<"no"<<endl;
			}
			else if( order=='I' )
			{
				// 连接两电脑
				combine(mac1,mac2);
			}
		}
	}
}


第二种,结构体:

/******************************************* 
******************************************** 
*           Author:Tree                    * 
*    From :  blog.csdn.net/lttree          * 
*      Title : 并查集:检查网络            * 
*    Source: 数据结构_课程设计             * 
*      Hint :  并查集                      * 
******************************************** 
*******************************************/ 

#include <iostream>
using namespace std;
#define MAX 10000

// 节点结构体
typedef struct node
{
	int data;
	int rank;
	int parent;
}UFSTree;

// 初始化函数
void MAKE_SET(UFSTree t[],int N)
{
	int i;
	for( i=1;i<=N;++i )
	{
		t[i].data=http://www.mamicode.com/i;>



***************************************转载请注明出处:http://blog.csdn.net/lttree********************************************

数据结构_课程设计——并查集:检查网络