在网上看到一个题目：

给定一个字符串的集合，格式如：。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出。

(1) 请描述你解决这个问题的思路；

(2) 给出主要的处理流程，算法，以及算法的复杂度；

(3) 请描述可能的改进。

其中一个解决方案是使用并查集，（数据结构中有，但已经忘了囧） 所以，百度了一下，主要参考了一个博主的

文章http://blog.csdn.net/dm_vincent/article/details/7655764  ，思路讲得很清楚，但是在代码实现上并不具一般应用性，为了再复习一下，用java泛型实现了一个并查集结构，可用于整数，字符串等等集合以及自定义数据类型。

Union_Find类：

package com.algorithms;

import java.util.HashMap;

/**
 * 并查集，数据结构
 * 采用泛型编程
 * 采用指向父节点方式实现，即map.get(key)的值是父节点的key，根节点的key和value相等，也是一个并查集的入口
 * @author "zhshl"
 * @date	2014-10-20
 *
 */
public class Union_Find<T> {
	private HashMap<T,T> unionMap=new HashMap<T, T>(); //记录节点之间的关系
	private  HashMap<T,Integer> unionSize=new HashMap<T, Integer>();///某个树的大小，某一个并查集的大小
	private int count=0;///并查集数目
	
 
	
	
	/**
	 * 获取并查集总数
	 * @return
	 */
	public int getCount(){
		return count;
	}
	
	/**
	 * 返回key属于的并查集的根的value,如果不存在key则返回NULL
	 * @param key
	 * @return
	 */
	public T find(T key){
		
		if(!unionMap.containsKey(key)){
			return null;
		}
		
		T value=http://www.mamicode.com/unionMap.get(key);>

测试代码类：
package com.algorithm.test;

import com.algorithms.Union_Find;

public class Union_Find_Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

			Union_Find<String> uf=new Union_Find<String>();
			uf.union("s1", "s2");
			uf.union("s3", "s4");
			uf.union("s1", "s3");
			
			uf.union("s5", "s6");
			uf.union("s6", "s7");
			
			String str1=uf.find("s5");
			String str2=uf.find("s2");
			
			
		/*	
			Union_Find<Integer> uf2=new Union_Find<Integer>();
			uf2.union(1, 2);
			uf2.union(3, 2);
			uf2.union(4, 2);
			uf2.union(5, 2);
			uf2.union(3, 5);
			uf2.union(2, 4);*/
			
			System.out.println(str1+":::::"+str2);
	}

}







并查集数据结构java源码