题意：
给出一堆木棍和两端的颜色，问能否将木棍连成一排，接头处两木棍的颜色相同
解法：
这题我开始大意了，直接按欧拉图的条件（应该说是否存在一个欧拉迹）判断奇数度的节点个数是否为0或2，没有考虑判断图的连通性
这里再次提醒自己
图里的问题注意首先判断连通性。
代码：
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