昆虫的同性恋

题目大意:
   输入一个数t，表示测试组数。然后每组第一行两个数字n,m，n表示有n只昆虫， 编号从1—n,m表示下面要输入m行交配情况，每行两个整数，表示这两个编号的昆虫为异性，要交配。 要求统计交配过程中是否出现冲突，即是否有两个同性的昆虫发生交配。
[输入输出]: [样例]:
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!

分析:
   一道并查集的练习题。将所有虫子分到两个集合中,公的一个集合,母的一个集合，读入一对信息时，判断它们是不是属于同一集合,是则发生同性恋.

import java.util.Scanner;

public class Main{
  private int n; 
  private int m;
  private int father[];
  private int other[]; //other[x]表示x的另一半是谁
  private int x[];
  private int y[];
  private boolean mark;

  public Main(int n,int m,int[] x,int[] y){
     this.n=n;
     this.m=m;
     this.x=x;
     this.y=y;
      father=new int[n+1];
        other=new int[n+1];
      
        for(int i=0;i<n+1;i++){
            father[i]=i;
            other[i]=0;
        }
        mark=false;
  }

   private int Find_Set(int x){ 
     int k,root; 
     root=x; 
     while(root!=father[root])  //循环找x的根      
         root=father[root]; 
     while(x!=root)//本循环修改查找路径中的所有节点使其指向根节点---压缩 
     { 
         k=father[x]; 
         father[x]=root;//指向根节点 
         x=k; 
     } 
     return x; 
    } 



  private void Union(int x,int y){
    int fx=Find_Set(x);
    int fy=Find_Set(y);
    father[fx]=fy;
}

 public void go(int d){
      
       int fx,fy,xl,yl;
        for(int l=1;l<=m;l++){
            xl=x[l];
            yl=y[l];
            if(!mark){
                fx=Find_Set(xl);
                fy=Find_Set(yl);
                if(fx==fy){//出现同性恋
                    mark=true;
                    break;
                }else{//没出现同性恋，合并。公的在一个集合，母的在另一个集合
                 
                  if(other[xl]!=0){
                        Union(other[xl],yl);
                  } else if(other[yl]!=0){
                        Union(other[yl],xl);
                  } else {
                   
                        other[xl]=yl;
                        other[yl]=xl;
                  }
                }
            }
        }
        System.out.println("Scenario #"+d+":");
        if(mark)
            System.out.println("Suspicious bugs found!");
        else
            System.out.println("No suspicious bugs found!");
        System.out.println();
     
  }

    public static void main(String[] args){
          Scanner in=new Scanner(System.in);
      int t,n,m;
      int[] x;
      int[] y;
      t=in.nextInt();
      for(int d=1;d<=t;d++){
        n=in.nextInt();
        m=in.nextInt();
        x=new int[m+1];
        y=new int[m+1];
        for(int l=1;l<=m;l++){
           x[l]=in.nextInt();
           y[l]=in.nextInt();
        }

       Main ma=new Main(n,m,x,y);
       ma.go(d);
     }
   }
 }

代码是AC了(POJ2492），差一点超时,以上代码是10976954_AC_9516MS_15372K.java,
大家有兴趣的,帮分析分析吧!