[자료구조] 08 과제

[Assignment]

import java.util.ArrayList;

public class Assignment {
	
	private final ArrayList<String> inputs;
	
	public Assignment(ArrayList<String> inputs) {
		this.inputs = inputs;
	}
	
	public void assignment() {
		int n = Integer.parseInt(inputs.get(0));
		Node[] nodes = new Node[n];
		for (int i=0; i<n; i++) {
			nodes[i] = new Node(i, 1);
		}
		UnionFind unionFind = new UnionFind(nodes);
		for (int l=1; l<inputs.size(); l++) {
			String[] temp = inputs.get(l).split(" ");
			int i = Integer.parseInt(temp[0]);
			int j = Integer.parseInt(temp[1]);
			unionFind.union(i, j);
		}
		unionFind.printsets();
	}
}

[UnionFind]

public class UnionFind {
	protected Node[] a;
	
	public UnionFind(Node[] array) {
		a = array;
	}
	
	protected int find(int i) {
		if (i != a[i].getParent())
			a[i].setParent(find(a[i].getParent()));
		return a[i].getParent();
	}
	
	public void union(int i, int j) {
		i = find(i);
		j = find(j);
		if (i == j) return;
		if (a[i].getSize() < a[j].getSize()) {
			int temp = i;
			i = j;
			j = temp;
		}
		a[j].setParent(i);
		a[i].setSize(a[i].getSize() + a[j].getSize());
	}
	
	public void printsets() {
		boolean[] visit = new boolean[a.length];
		System.out.println("[disjoint sets]");
		for (int i=0; i<a.length; i++) {
			a[i].setParent(find(a[i].getParent()));
			if (visit[a[i].getParent()]) continue;
			visit[a[i].getParent()] = true;
			for (int j=0; j<a.length; j++) {
				a[j].setParent(find(a[j].getParent()));
				if (a[i].getParent() == a[j].getParent()) {
					System.out.print(j + " ");
				}
			}
			System.out.println();
		}
	}
}