并查集合并：
int fx,fy;
fx=find(x);
fy=find(y);

if(fx!=fy)fa[x]=fy;//WA!!!
if(fx!=fy)fa[y]=fx;//AC!!!

不信可以试试下面的代码



import java.io.BufferedReader;
import java.io.IOException;


import java.io.PrintWriter;

import java.io.InputStreamReader;
import java.util.*;
public class Main{
static String str,ex,ey,stack[];
static Map<String,Integer> map = new HashMap<String,Integer>();
static int x,y,top,fa[],deg[];
static int find(int x){
	if(fa[x]!=x)return find(fa[x]);
	return fa[x];
}
static boolean judge(){
	int x=-1;
	for(int i=0;i<map.size();i++){
		if(x==-1)x=find(i);
		else if(x!=find(i))return false;
	}
	return true;
}
public static void  main(String args[]) throws IOException{ 
    BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
    str=re.readLine();
    fa=new int[500100];
    deg=new int[500100];
    for(int i=0;i<500100;i++){deg[i]=0;fa[i]=i;}
    top=0;
    while(str!=null){
    	ex=str.split(" ")[0];
    	ey=str.split(" ")[1];
    	//if(ex.equals("fuck"))break;
    	if(map.containsKey(ex))x=map.get(ex);
    	else{map.put(ex,map.size());x=map.size()-1;}
    	if(map.containsKey(ey))y=map.get(ey);
    	else{map.put(ey,map.size());y=map.size()-1;}
    	deg[x]++;
    	deg[y]++;
        int fx,fy;
        fx=find(x);
        fy=find(y);
        if(fx!=fy)fa[y]=fx;
    	str=re.readLine();
    }
      // for(int i=0;i<map.size();i++)System.out.println(i+" "+deg[i]);
     if(!judge())System.out.println("Impossible");
     else{
    	int odd=0;
    	for(int i=0;i<map.size();i++)
    		if(deg[i]%2==1)odd++;
    	if(odd<=2)System.out.println("Possible");
    	else System.out.println("Impossible");
     }
  }  
}

• Re:WA10次，错在这里？求大神解答， (49) dongshimou 2014-07-07 01:08:23