UVa-10129

欧拉回路，然后dfs判断是否联通。（新技能get）

注意:在dfs判断是否联通的时候，要是写成有向图的话，则一定要从起点进行dfs，有不少博主写错了，由于这题UVa的数据貌似不强，所以也AC了==

我写的是无向图。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=100010;
 6 const int maxx=1010;
 7 const int maxm=260;
 8 bool g[maxm][maxm];
 9 int in[maxm],out[maxm];
10 bool vis[maxm];
11 char s[maxx];
12 void dfs(int u)
13 {
14     cout<<(char)u<<endl;
15     vis[u]=1;
16     for(int i='a';i<='z';i++)
17         if(g[u][i]&&!vis[i]) dfs(i);
18 }
19 int main()
20 {
21     int T;
22     scanf("%d",&T);
23     while(T--)
24     {
25         memset(g,0,sizeof(g));
26         memset(in,0,sizeof(in));
27         memset(out,0,sizeof(out));
28         memset(vis,0,sizeof(vis));
29         int n;
30         scanf("%d",&n);
31         for(int i=1;i<=n;i++)
32         {
33             scanf("%s",s);
34             int len=strlen(s);
35             g[s[0]][s[len-1]]=g[s[len-1]][s[0]]=1;
36             in[s[0]]++;
37             out[s[len-1]]++;
38         }
39         bool flag=1;
40         int cnt=0,judge[maxm]={};
41         for(int i='a';i<='z';i++)
42             if(in[i]!=out[i]) judge[++cnt]=in[i]-out[i];
43         if(cnt>2) flag=0;
44         else if(cnt==2)
45         {
46             if((judge[1]==1&&judge[2]==-1)
47                ||(judge[1]==-1&&judge[2]==1))
48                 flag=1;
49             else flag=0;
50         }
51         if(flag==0)
52         {
53             printf("The door cannot be opened.
");
54             continue;
55         }
56         dfs(s[0]);
57         flag=1;
58         for(int i='a';i<='z';i++)
59         {
60             if((in[i]!=0||out[i]!=0)&&vis[i]==0)
61             {
62                 flag=0;
63                 break;
64             }
65         }
66         if(flag) printf("Ordering is possible.
");
67         else printf("The door cannot be opened.
");
68     }
69 }