游客 Signup | Login
中文 | En

1357 - 算法6-8~6-11：用树表示的等价问题

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 32 MB
在离散数学中，对等价关系和等价类的定义是：
如果集合S中的关系R是自反的、对称的和传递的，则称它为一个等价关系。
等价关系是现实世界中广泛存在的一种关系，许多应用问题可以归结至等价类问题，这类问题通常被称为等价问题。
通过使用集合，能够解决等价问题。而集合可以通过双亲表示法的树结构进行保存。通过对树结构的操作，可以实现查找、归并等操作。查找操作和归并操作的算法如下： 

<span style="font-family:宋体;">在以上的归并操作中，由于表示集合的树的深度与树形成的过程有关，因此在最坏情况下全部归并操作将会有</span><span>O(n<sup>2</sup>)</span><span style="font-family:宋体;">的复杂度。而通过在归并时比较子集所含成员的数目，令成员少的归并至成员多的集合，将能够提高算法的效率。下面给出优化的归并操作算法：</span>


<img src="http://tk.hustoj.com:80/upload/pimg1759_2.png" width="563" height="234" alt="" />


<span style="font-family:宋体;">另外，通过增加“压缩路径”的功能，即将所有从根到相应元素路径上的元素都变成树根的孩子。算法如下所示：</span>


<img src="http://tk.hustoj.com:80/upload/pimg1759_3.png" width="531" height="180" alt="" />


<span style="font-family:宋体;">本题中，将会给出</span><span>n</span><span style="font-family:宋体;">个原本互不相交的集合及</span><span>k</span><span style="font-family:宋体;">次集合合并的操作。通过这</span><span>k</span><span style="font-family:宋体;">次合并，判断最终的某两个原始的集合是否被合并成了同一个集合。</span>


<span></span>


<span></span>


<span></span>

Input

输入的第一行包含两个用空格隔开的正整数n和k，其中n不超过100，k不超过n-1。
之后的k行中，每行包含两个用空格隔开的正整数x和y，表示将x元素所在的集合和y元素所在的集合合并至同一个集合。保证x和y均在1至n之间。
最后一行中，包含两个正整数，表示需要判断是否在同一个集合的元素编号。

Output

共一行，包含字符串“YES”或“NO”，“YES”表示需判断的元素在同一个集合中，“NO”表示不在同一个集合中。请注意不需要输出引号，且行尾输出换行。

Examples

Input Format

5 2
1 3
2 3
1 2

Output Format

YES

Solution C

#include<stdio.h>
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	int x[100],y[100],i;
	for(i=0;i<k;i++)
		scanf("%d%d",&x[i],&y[i]);
	int x1,y1;
	scanf("%d%d",&x1,&y1);
	int flag=0;
	for(i=0;i<k;i++)
	{
		if(x1==x[i]||x1==y[i])
		{
			flag=1;
				break;
		}
	}
	if(flag==1)
		for(i=0;i<k;i++)
			{
			if(y1==x[i]||y1==y[i])
			{
				flag=2;
					break;
			}
		}
	if(flag==2)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

Solution C++

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAX_TREE_SIZE 100
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char TElemType;
typedef struct {
	TElemType data;
	int parent; /* 双亲位置域 */
} PTNode;
typedef struct {
	PTNode nodes[MAX_TREE_SIZE+1];
	int n; /* 结点数 */
} PTree;
typedef PTree MFSet;
int find_mfset(MFSet S, int i) {  // 算法6.8
   // 找集合S中i所在子集的根
   int j;
   if (i<1 || i>S.n) return -1;   // i不是S中任一子集的成员
   for (j=i; S.nodes[j].parent>0; j=S.nodes[j].parent);
   return j;
}// find_mfset
Status merge_mfset(MFSet &S, int i, int j) {  // 算法6.9
   // S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点。
   // 求并集Si∪Sj。
   if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;
   S.nodes[i].parent = j;
   return OK;
} // merge_mfset
Status mix_mfset(MFSet &S, int i, int j) {  // 算法6.10
	// S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点
	// 求并集Si∪Sj。
	if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;
	if (S.nodes[i].parent>S.nodes[j].parent) {   // Si所含成员数比Sj少
		S.nodes[j].parent+=S.nodes[i].parent;
		S.nodes[i].parent=j;
	} else {                                     // Sj的元素比Si少
		S.nodes[i].parent+=S.nodes[j].parent;
		S.nodes[j].parent=i;
	}
	return OK;
} // mix_mfset
int fix_mfset(MFSet &S, int i) {  // 算法6.11
	// 确定i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。
	int j,k,t;
	if (i<1 || i>S.n) return -1;       // i 不是S中任一子集的成员
	for (j=i; S.nodes[j].parent>0; j=S.nodes[j].parent);
	for (k=i; k!=j; k=t) {
		t=S.nodes[k].parent;  S.nodes[k].parent=j;
	}
	return j;
} // fix_mfset
int main() {
	int n,i,x,y,k;
	MFSet Set;
	scanf("%d%d", &n, &k);
	Set.n = n;
	for(i=1;i<=n;i++) {
		Set.nodes[i].data=i;
		Set.nodes[i].parent=-1;
	} // 建立n个只有一个元素的集合
	for(i=1;i<=k;i++) {
		scanf("%d%d", &x, &y);
		x = find_mfset(Set, x); // 找到子集的根节点
		y = find_mfset(Set, y); // 找到子集的根节点
		mix_mfset(Set, x, y);
		fix_mfset(Set, x);
		fix_mfset(Set, y);
	}
	scanf("%d%d", &x, &y);
	x = find_mfset(Set, x); // 找到子集的根节点
	y = find_mfset(Set, y); // 找到子集的根节点
	if (x == y)
		puts("YES");
	else
		puts("NO");
	return 0;
}
请先登陆