***************************************转载请注明出处：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********************************************
数据结构_课程设计——并查集：检查网络