| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA10次,错在这里?求大神解答,并查集合并: 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"); } } } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator