https://d19vezwu8eufl6.cloudfront.net/algs4partI/slides%2F15UnionFind.pdf

DynamicConnect.java

package sandbox;

import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

/**
 * @author Keesun Baik
 */
public class DynamicConnect {

	int size;
	List<List<Integer>> groups;

	public DynamicConnect(int size) {
		this.size = size;
		groups = new ArrayList<>();
		for(int i = 0 ; i < size ; i++) {
			ArrayList<Integer> integers = new ArrayList<>();
			integers.add(i);
			groups.add(integers);
		}
	}

	public void connect(int a, int b) {
		List<Integer> aGroup = findGroup(a);
		List<Integer> bGroup = findGroup(b);
		merge(aGroup, bGroup);
	}

	private void merge(List<Integer> aGroup, List<Integer> bGroup) {
		// make newGroups
		List<List<Integer>> newGroups = new ArrayList<>();
		for(List<Integer> group : groups) {
			if(group != aGroup && group != bGroup) {
				newGroups.add(group);
			}
		}

		// merge two groups
		List<Integer> mergedGroup = new ArrayList<>();
		for(Integer value : aGroup) {
			mergedGroup.add(value);
		}
		for(Integer value : bGroup) {
			mergedGroup.add(value);
		}

		// replace to newGroups
		this.groups = newGroups;
		this.groups.add(mergedGroup);
	}

	private List<Integer> findGroup(int value) {
		for(List<Integer> group : groups) {
			if(group.contains(value)) {
				return group;
			}
		}
		return null;
	}

	public boolean connected(int a, int b) {
		boolean result = false;
		List<Integer> group = findGroup(a, b);
		if(group != null) {
			result = true;
		}
		return result;
	}

	private List<Integer> findGroup(int a, int b) {
		for(List<Integer> group : groups) {
			if(group.contains(a) && group.contains(b)) {
				return group;
			}
		}
		return null;
	}

	public static class DynamicConnectTest {
		@Test
		public void simpleConnect(){
			DynamicConnect app = new DynamicConnect(10);
			app.connect(0, 1);
			assertThat(app.connected(0, 1), is(true));
			assertThat(app.connected(0, 2), is(false));
		}

		/**
		 * Slide 4
		 */
		@Test
		public void complexConnecy(){
			DynamicConnect app = new DynamicConnect(10);
			app.connect(4, 3);
			app.connect(3, 8);
			app.connect(6, 5);
			app.connect(9, 4);
			app.connect(2, 1);
			assertThat(app.connected(0, 7), is(false));
			assertThat(app.connected(8, 9), is(true));
			app.connect(5, 0);
			app.connect(7, 2);
			app.connect(6, 1);
			app.connect(1, 0);
			assertThat(app.connected(0, 7), is(true));
		}
	}


}