cubestacking.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 88 行

package PKU.Unionfindsets;
import java.util.Scanner;

/**
 * ID:1988
 * 并查集
 * @author yhm
 *
 */
public class CubeStacking {

	static CubeNode[] cubes = new CubeNode[30000];

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int P = cin.nextInt();
		makeSet();
		for (int i = 0; i < P; i++) {
			String str = cin.next();
			if (str.equals("M")) {
				int x = cin.nextInt() - 1;
				int y = cin.nextInt() - 1;
				union(x, y);
			} else {
				int x = cin.nextInt() - 1;
				find(x);
				System.out.println(cubes[x].behind);
			}
		}

	}

	static void makeSet() {
		for (int i = 0; i < 30000; i++) {
			cubes[i] = new CubeNode(-1, 1, 0);
		}
	}

	static int find(int x) {
		int r = x;
		int j;

		while (cubes[r].parent != -1)
			// 找出结点x所在树的根结点r
			r = cubes[r].parent;

		while (x != r)
		{
			int q = cubes[x].parent;// 路径压缩
			cubes[x].parent = r;
			j = q;
			do {// 迭代求出路径上每一个子结点相对于r的相对位置
				cubes[x].behind += cubes[j].behind;
				j = cubes[j].parent;
			} while (j != -1);
			x = q;
		}

		return r;
	}

	static void union(int a, int b) {
	    int t1,t2;
	    t1=find(a);//计算a所在树的根结点t1
	    t2=find(b);//计算b所在树的根结点t2
	    cubes[t1].parent=t2;//将t1的父结点设为t2
	    cubes[t1].behind=cubes[t2].num;//计算t1的相对位置为num[t2]
	    cubes[t2].num+=cubes[t1].num; //计算新集合的结点数 
	}

}

class CubeNode {
	int parent;
	int num;
	int behind;

	public CubeNode(int parent, int num, int behind) {
		super();
		this.parent = parent;
		this.num = num;
		this.behind = behind;
	}

}