链接:http://vjudge.net/problem/viewProblem.action?id=18806
描述:给出一堆珠子,每个珠子有两种颜色,有一端颜色相同的珠子可以串在一起,问是否可以把所有珠子串在一起,并求其中一种方案。
思路:欧拉回路
以颜色作为节点,以珠子作为边建图,无向图。
下面是我的实现:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 #define MaxC 55
6 int Edge[MaxC][MaxC],Du[MaxC];
7 int M,Cnt;
8 bool vis[MaxC][MaxC];
9 inline void Addedge(int u,int v)
10 {
11 Edge[u][v]++;Edge[v][u]++;
12 }
13 void Solve(int u)
14 {
15 int v;
16 for(v=1;v<=M;)
17 {
18 if(Edge[u][v])
19 {
20 // vis[u][v]=vis[v][u]=1;
21 Edge[u][v]--;Edge[v][u]--;
22 Solve(v);
23 printf("%d %d",v,u);
24 if(u!=M)
25 printf("\n");
26 if(u==M)
27 {
28 Cnt--;
29 if(Cnt)
30 printf("\n");
31 }
32 }
33 else v++;
34 }
35 }
36 int main()
37 {
38 int T,N;
39 int i,j,u,v;
40 scanf("%d",&T);
41 for(i=1;i<=T;i++)
42 {
43 if(i>1) printf("\n");
44 printf("Case #%d\n",i);
45 scanf("%d",&N);
46 memset(Du,0,sizeof(Du));
47 memset(Edge,0,sizeof(Edge));
48 memset(vis,0,sizeof(vis));
49 M=0;
50 for(j=1;j<=N;j++)
51 {
52 scanf("%d%d",&u,&v);
53 Addedge(u,v);
54 Du[u]++;Du[v]++;
55 if(M<u) M=u;
56 if(M<v) M=v;
57 }
58 for(j=1;j<=M;j++)
59 if(Du[j]%2)
60 break;
61 if(j<=M)
62 {
63 printf("some beads may be lost\n");
64 continue;
65 }
66 Cnt=Du[M];
67 Solve(M);
68 }
69 return 0;
70 }
给一个我写的数据生成器:http://www.cnblogs.com/CQBZOIer-zyy/p/3818078.html