A Bug's Life
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6595 Accepted Submission(s): 2154

?

Problem Description
Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.

Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

?

Input
The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

Output
The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.

Sample Input
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

Sample Output
Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!

?

?

题意：判断每组数据，是否有 同性恋

?

方法一：并查集+BFS（广度优先搜索）

?

?

import java.io.*;
import java.util.*;
public class Main {
	int M=2001,t,n,m;
	int sex[]=new int[M];
	int patten[]=new int[M];
	int map[][]=new int[M][M];
	Queue que=new LinkedList();
	public static void main(String[] args) {
		new Main().work();
	}
	void work(){
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		t=sc.nextInt();
		for(int i=1;i<=t;i++){
			n=sc.nextInt();
			m=sc.nextInt();
			init();
			for(int j=0;j 
 
import java.io.*;
import java.util.*;

public class Main {
	int t, n, m, max = 2010;
	int patten[] = new int[max];
	int sex[] = new int[max];
	boolean boo;
	public static void main(String[] args) {
		new Main().work();
	}
	void work() {
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		t = sc.nextInt();
		for (int i = 1; i <= t; i++) {
			n = sc.nextInt();
			m = sc.nextInt();
			init();
			for (int j = 0; j < m; j++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				if (find(a) == find(b)){// 找到他们的祖先，如果性别相同，则是同性恋
					boo = true;
				}
				else {
					if (sex[a] == 0) sex[a] = b;//如果虫子的性别没有确定，设它的性别与另外一个虫子的性别相反,划分的一个集合中去
					else union(sex[a], b);//如果虫子的性别确定了，找到它的祖先，并划分的一个集合中去
					
					if (sex[b] == 0) sex[b] = a;//同上
					else union(sex[b], a);
				}

			}
			System.out.println("Scenario #"+i+":");
			if (boo == true)
				System.out.println("Suspicious bugs found!");  
			else
				System.out.println("No suspicious bugs found!");  

			System.out.println();

		}
	}
	//并查集的合并
	void union(int a,int b){
		int pa=find(a);
		int pb=find(b);
		if(pa==pb)
			return;
		patten[pa]=pb;
	}
	//并查集的查找
	int find(int x){
		if(patten[x]==x)
			return x;
		patten[x]=find(patten[x]);//路径压缩
		return patten[x];
	}
	//初始化
	void init(){
		boo = false;
		Arrays.fill(sex,0);
		for (int k = 1; k<= n; k++) {
			patten[k] = k;
		}
	}
}
 
 
import java.io.*;
import java.util.*;
public class Main {
	int t,n,m,max=2001;
	int patten[]=new int[max];
	int opp[]=new int[max];
	boolean boo;
	public static void main(String[] args) {
		new Main().work();
	}
	void work(){
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		t=sc.nextInt();
		for(int i=0;i 
 
?