題意：
給出一堆木棍和兩端的顏色，問(wèn)能否將木棍連成一排，接頭處兩木棍的顏色相同
解法：
這題我開(kāi)始大意了，直接按歐拉圖的條件（應(yīng)該說(shuō)是否存在一個(gè)歐拉跡）判斷奇數(shù)度的節(jié)點(diǎn)個(gè)數(shù)是否為0或2，沒(méi)有考慮判斷圖的連通性
這里再次提醒自己
圖里的問(wèn)題注意首先判斷連通性。
代碼：
1
import java.io.*;
2import java.util.*;
3
public class Main 
{
4
5
/** *//**
6 * @param args
7
*/
8 static int pre[]=new int[510000];
9 static int find(int pos)
10 {
11 if(pre[pos]==pos) return pos;
12 else
13 {
14 pre[pos]=find(pre[pos]);
15 return pre[pos];
16 }
17 }
18 static void union(int t1,int t2)
19 {
20 pre[find(t1)]=find(t2);
21 }
22 public static void main(String[] args) throws IOException{
23 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
24 HashMap<String,Integer> count=new HashMap<String,Integer>();
25 HashMap<String,Integer> id=new HashMap<String,Integer>();
26 int c=0;
27 while(in.nextToken()!=in.TT_EOF)
28 {
29 String t1=in.sval;
30 if(count.containsKey(in.sval))
31 count.put(in.sval, count.get(in.sval)+1);
32 else
33 {
34 pre[c]=c;
35 id.put(in.sval, c++);
36
37 count.put(in.sval, 1);
38 }
39 in.nextToken();
40 if(count.containsKey(in.sval))
41 count.put(in.sval, count.get(in.sval)+1);
42 else
43 {
44 pre[c]=c;
45 id.put(in.sval, c++);
46 count.put(in.sval, 1);
47 }
48 union(id.get(t1),id.get(in.sval));
49 }
50 int total=1;
51 for(int i=1;i<c;i++)
52 if(find(i)!=find(i-1))
53 total++;
54 if(total>1)
55 {
56 System.out.println("Impossible");
57 return;
58 }
59 total=0;
60 for(int p:count.values())
61 if(p%2==1) total++;
62 if(total!=0&&total!=2)
63 System.out.println("Impossible");
64 else
65 System.out.println("Possible");
66
67 }
68
69
}
70