HDU 1829 A Bug's Life (并查集+BFS（广度优先搜索）)
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;
}
}
}
补充：软件开发 , C++ ,
