划分等价类实现过程

百度的一个笔试题目：

百度全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友；接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。

例如：

<小明，小王>，<小军，小王>，<小丽，小李>是队友，那么小军和小明是队友，小军和小丽不是队友。

这道题目可以用图的连通性来解决，但是稍微复杂了些哈，下面提供划分等价类的方法，

划分等价类的过程，确定等价类的算法如下：
   1 令S中每个元素各自形成一个只含有单个成员的子集，记作S1、S2.。。。
   2 重复读入m个偶对，对每个偶对（x，y），判断x和y所属的子集，如果属于同一子集，则不做任何操作，否则，将两个子集合并。
    我们可以用树形结构来表示集合，每个节点含有指向双亲的指针，并约定根结点的成员兼做子集的名称，则实现并操作时，只需要将一颗子集树指向另一棵子集树的根即可；同时，完成某个元素所在集合的查找，只要从该成员节点出发，顺链向上直至找到树的根结点为止。
    以下例子使用整型数组表示集合，数组中的值表示结点的父节点或者表示该集合中的元素数目的相反数（当该节点为根结点时）。

public class UnionSearch {
		public static void main(String[] args) {
		// TODO Auto-generated method stub
		int numberset[] =new int[10];
		for(int i=0;i<numberset.length;i++){//初始时所有值均为1，表示每个元素为一个集合
			numberset[i]=-1;
		}
		merge_set(numberset,1,2);
		merge_set(numberset,3,4);
		merge_set(numberset,6,5);
		merge_set(numberset,7,8);
		merge_set(numberset,1,3);
		merge_set(numberset,5,7);
		//mergeunion(union,1,5);
		
		for(int i=1;i<9;i++){
			for(int j=i+1;j<9;j++){
				System.out.println(i+" 和"+j+"在一个集合吗？"+isInOneGroup(numberset,i,j));
			}
		}
		
	}
	
	/*
	 * 将i与j合并，如果i与j分别属于不同的集合中，则将两个集合合并，
	 * 合并的过程是，将i所属集合的父节点指向j所属集合的父节点的序号，
	 * 或者j所属集合的父节点执行i所属结合的父节点的序号
	 * 每个集合的父节点存储的值为该集合中所含元素的个数的相反数，其余节点存储的值为父节点
	 */
	public static void merge_set(int []union,int i,int j ){
		if(i<1||i>union.length||j<1||j>union.length){
			System.out.println("i or j 's scole is error");
			return;
		}
		int ip=getparent(union,i);
		int jp=getparent(union,j);
		
		if(ip!=jp && ip!=0 && jp!=0){
			if(ip>jp){
				union[ip]+=union[jp];
				union[jp]=ip;
			}else{
				union[jp]+=union[ip];
				union[ip]=jp;
			}
		}
	}
	/*
	 * 查找第i个元素所属的集合，返回该集合的父节点序号
	 */
	public static int getparent(int []union,int i){
		int j=0;
		for(j=i;union[j]>0;j=union[j]);
		return j;
	}
	
	/*
	 * 判断i和j是在同一个集合吗
	 *
	 */
	public static boolean isInOneGroup(int union[],int i,int j){
		if(getparent(union,i)==getparent(union,j)){
			return true;
		}
		return false;
	}
}

 

将题目中的名字使用序号来表示就可以了，当然这个过程也可以再优化。