abugslife.java

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

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

/**
 * ID：2492
 * 并查集算法
 * @author yhm
 *
 */
public class ABugsLife {

	static BugNode[] bugs;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for (int i = 1; i <= caseNum; i++) {
			int n = cin.nextInt();
			int m = cin.nextInt();

			boolean flag = false;
			Make_set(n);
			for (int j = 0; j < m; j++) {
				int x = cin.nextInt() - 1;
				int y = cin.nextInt() - 1;

				if(flag) continue;
				
				int a = Find_set(x);

				int b = Find_set(y);

				if (a == b)//两只虫在同一集合中则有同性恋虫的怀疑

					flag = true;

				if (bugs[x].opposite != x)

					Union(b, bugs[x].opposite);

				else

					bugs[x].opposite = b;

				if (bugs[y].opposite != y)

					Union(a, bugs[y].opposite);

				else

					bugs[y].opposite = a;

			}
			System.out.println("Scenario #" + i + ":");
			System.out.println(flag ? "Suspicious bugs found!"
					: "No suspicious bugs found!");
			System.out.println();

		}
	}

	static void Make_set(int n) //初始化，产生n个集合，每个集合一只虫

	{
		bugs = new BugNode[n];
		for (int i = 0; i < n; i++)

		{
			bugs[i] = new BugNode();

			bugs[i].rank = 0;

			bugs[i].parent = i;

			bugs[i].opposite = i;

		}

	}

	static int Find_set(int x) //寻找根节点，路径压缩

	{

		if (x != bugs[x].parent)

			bugs[x].parent = Find_set(bugs[x].parent);

		return bugs[x].parent;

	}

	static void Union(int x, int y) //合并相同集合，按秩合并

	{

		int a = Find_set(x);

		int b = Find_set(y);

		if (bugs[a].rank > bugs[b].rank)

			bugs[b].parent = a;

		else

			bugs[a].parent = b;

		if (bugs[x].rank == bugs[y].rank)

			bugs[y].rank++;

	}

}

class BugNode {
	int rank;
	int parent;
	int opposite;
}