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<Integer> que=new LinkedList<Integer>();
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();
map[a][b]=map[b][a]=1;
union(a,b);
}
System.out.println("Scenario #"+i+":");
if(BFS()){
System.out.println("Suspicious bugs found!");
}
else{
System.out.println("No suspicious bugs found!");
}
System.out.println();
}
}
//深度優先搜索
boolean BFS(){
//將不在集合裡，加入隊列中
for(int i=1;i<=n;i++){
if(i==patten[i]){
sex[i]=1;
que.add(i);
}
}
while(!que.isEmpty()){
int t=que.poll();
for(int i=1;i<=n;i++){
if(map[t][i]!=0){
if(sex[i]==0){
if(sex[t]==1) sex[i]=2;//如果性別沒有確定的 設為 異性
else if(sex[t]==2) sex[i]=1;
que.add(i);//加入隊列
}else{
if(sex[t]==sex[i]) return true;//如果性別相同，則是同性戀。
}
}
}
}
return false;
}
//並查集合並
void union(int a,int b){
int pa=find(a);
int pb=find(b);
if(pa!=pb){
patten[pa]=pb;
}
}
//並查集查找
int find(int x){
if(patten[x]==x)
return x;
patten[x]=find(patten[x]);//路徑壓縮
return patten[x];
}
//初始化
void init(){
que.clear();
Arrays.fill(sex,0);
for(int i=0;i<=n;i++){
patten[i]=i;
Arrays.fill(map[i],0);
}
}
}
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<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(opp[a]==-1&&opp[b]==-1){// 如果ab都沒有出現過設置他們唯一性，劃分到一個集合中去
opp[a]=b;
opp[b]=a;
}
else if(opp[a]==-1){//如果a沒有出現，設置它和另外一個為異性。劃分到一個集合中去，同時更新它們的祖先並劃分到一個集合中區
opp[a]=b;
union(a,opp[b]);//更新它們的祖先並劃分到一個集合中區
}
else if(opp[b]==-1){//同上
opp[b]=a;
union(b,opp[a]);
}
else{
if(find(a)==find(b)) boo=true;//找到他們的祖先性別相同，則為同性戀
else{
union(a,opp[b]);//更新它們的祖先並劃分到一個集合中區
union(b,opp[a]);//更新它們的祖先並劃分到一個集合中區
}
}
}
System.out.println("Scenario #"+(i+1)+":");
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;
for(int i=1;i<=n;i++){
patten[i]=i;
opp[i]=-1;
}
}
}
