欧拉回路问题。
题意是说给你一些字符串。类似于成语接龙，上一个字符串尾字母必须和下一个字符串首字母同样。
把全部字符串连成一串。
依据定理推断欧拉通路。然后DFS判连通（并查集也可）
没注意题意 字符串开了str[100] 结果RE。结果字符串最长有1000.改了就AC了。
DFS:
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int n,m;
int g[27][27];
int in[27],out[27];
bool vis[27];
int start;
bool Euler()
{
int I=0,O=0;
for(int i=0; i<26; i++)
{
if(in[i]==out[i]+1)I++;
else if(out[i]==in[i]+1)O++,start=i;
else if(in[i]!=out[i])return 0;
}
if((I==0&&O==0)||(I==1&&O==1))return 1;
return 0;
}
void dfs(int i)
{
int j;
for( j=0; j<26; j++)
{
if(g[i][j]==0)continue;
g[i][j]--;
vis[i]=vis[j]=1;
dfs(j);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
char str[1001];
memset(g,0,sizeof(g));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=0; i<m; i++)
{
scanf("%s",str);
int u=str[0]-'a';
int v=str[strlen(str)-1]-'a';
g[u][v]++;
in[v]++,out[u]++;
}
for(int i=0;i<26;i++)
if(out[i]>0){start=i;break;}
bool flag=1;
flag=Euler();
if(!flag)
{
puts("The door cannot be opened.");
continue;
}
memset(vis,0,sizeof(vis));
dfs(start);
for(int i=0; i<26; i++)
{
if(in[i]||out[i])
{
if(vis[i]==0)
{
flag=0;
break;
}
}
}
if(flag)puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
}
并查集：
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int in[26],out[26];
int fa[26];
int n;
bool vis[26];
int father(int x)
{
if(x!=fa[x])
return fa[x]=father(fa[x]);
}
bool Euler()
{
int I=0,O=0;
for(int i=0;i<26;i++)
{
if(!vis[i]||in[i]==out[i])continue;
if(out[i]-1==in[i])O++;
else if(in[i]-1==out[i])I++;
else return 0;
}
if(O==1&&I==1)return 1;
if(O==0&&I==0)return 1;
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=0;i<26;i++)
{
in[i]=out[i]=vis[i]=0;
fa[i]=i;
}
scanf("%d",&n);
char str[1001];
for(int i=0;i<n;i++)
{
scanf("%s",str);
int len=strlen(str);
int u=str[0]-'a';
int v=str[len-1]-'a';
vis[u]=vis[v]=1;
out[u]++,in[v]++;
u=father(u),v=father(v);
if(u==v)continue;
fa[v]=u;
}
bool flag=0;
flag=Euler();
if(!flag)
{
puts("The door cannot be opened.");
continue;
}
else
{
int block=0;
for(int i=0;i<26;i++)
{
if(vis[i]&&father(i)==i)block++;
if(block>1){flag=0;break;}
}
if(!flag)puts("The door cannot be opened.");
else puts("Ordering is possible.");
}
}
}