findthemcatchthem.java

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

package PKU.Unionfindsets;

import java.util.*;

/**
 * ID:1703
 * @author yhm
 *
 */
public class FindthemCatchthem {

	static final int MaxN = 100001;
	static int[] father = new int[MaxN], rank = new int[MaxN],
			opp = new int[MaxN];

	static int find_set(int x) {
		if (x == -1)
			return -1;
		int temp = x;
		while (father[x] != x){
			x = father[x];
		}
		int result = x;
		x = temp;
		while (father[x] != x){
			temp = father[x];
			father[x] = result;
			x = temp;
		}
		return result;
	}

	static int merge_set(int x, int y) {
		if (x == -1)
			return y;
		if (y == -1)
			return x;
		if (rank[x] > rank[y]) {
			father[y] = x;
			return x;
		} else {
			father[x] = y;
			if (rank[x] == rank[y])
				rank[y]++;
			return y;
		}
	}

	static void difference(int x, int y) {
		int tx, ty;
		x = find_set(x);
		y = find_set(y);
		tx = merge_set(opp[x], y);
		ty = merge_set(x, opp[y]);
		opp[tx] = ty;
		opp[ty] = tx;
	}

	static void makeSet(int n) {
		for (int i = 1; i <= n; i++) {
			father[i] = i;
			rank[i] = 0;
			opp[i] = -1;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		//long time = System.currentTimeMillis();
		for (int i = 1; i <= caseNum; i++) {
			int n = cin.nextInt();
			int m = cin.nextInt();
			makeSet(n);
			for (int j = 0; j < m; j++) {
				String str = cin.next();
				int x = cin.nextInt();
				int y = cin.nextInt();

				if (str.equals("A")) {
					x = find_set(x);
					y = find_set(y);
					if (x == y)
						System.out.println("In the same gang.");
					else if (x == opp[y])
						System.out.println("In different gangs.");
					else
						System.out.println("Not sure yet.");
				} else if (str.equals("D")) {
					difference(x, y);
				}

			}
		}
		//System.out.println( System.currentTimeMillis()-time);

	}

}