findthemcatchthem1.java

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

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


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

	
	static Node[] criminals = new Node[100000];
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		for(int i=0;i<100000;i++){
			criminals[i]=new Node(0,i,i);		
		}
		long time = System.currentTimeMillis();
		int caseNum = cin.nextInt();
		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()-1;
				int y = cin.nextInt()-1;
				if(str.equals("D")){
					
					int a = find(x);

					int b = find(y);

					int tx=-1,ty=-1;

					if (criminals[x].opposite != x)
						union(b, criminals[x].opposite);
					else
						criminals[x].opposite = b;

					if (criminals[y].opposite != y)
						union(a, criminals[y].opposite);
					else
						criminals[y].opposite = a;
					
					
					if(tx!=-1 && ty!=-1){
						criminals[tx].opposite = ty;
						criminals[ty].opposite = tx;
					}
					
				}
				else{
	
					int a = find(x);
					int b = find(y);
					
					if(a == b){						
						System.out.println("In the same gang.");			
					}
					else if(a == find(criminals[b].opposite)){
						System.out.println("In different gangs.");
					}
					else{
						System.out.println("Not sure yet.");
					}
					
				}
			}
		}
		System.out.println( System.currentTimeMillis()-time);

	}

	static void makeSet(int n){
		
		for(int i=0;i<n;i++){
			criminals[i].opposite = i;
			criminals[i].parent = i;
			criminals[i].rank = 0;			
		}
	}
	static int find(int x){
		if (x != criminals[x].parent)

			criminals[x].parent = find(criminals[x].parent);

		return criminals[x].parent;
	}
	static int union(int x, int y){
		x = find(x);
		y = find(y);
		if(x==y) return x;
		if(criminals[x].rank > criminals[y].rank){
			criminals[y].parent = x;
			return x;
		}
		else if(criminals[x].rank < criminals[y].rank){
			criminals[x].parent = y;
			return y;
		}
		else{
			criminals[x].parent = y;
			criminals[y].rank++;
			return y;
		}
		
		
	}
	
	
}


class Node{
	int rank;
	int parent;
	int opposite;
	public Node(int rank, int parent, int opposite) {
		super();
		this.rank = rank;
		this.parent = parent;
		this.opposite = opposite;
	}
	
}