原题链接
考察:欧拉路径
思路:
??有向图存在欧拉路径:所有点入度 = 出度或除两个外入度 = 出度.
??但此条件有个大前提就是边连通,判断边连通需要:并查集或者dfs
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010,M = 1010,S = 30;
int n,din[S],dout[S],p[S];
bool vis[S];
char s[M];
int findf(int x)
{
if(p[x]!=x) p[x] = findf(p[x]);
return p[x];
}
bool check()
{
int cnt = 0,fa = -1;
for(int i=0;i<26;i++)
if(vis[i])
{
if(fa==-1) fa = findf(i);
else if(fa!=findf(i)) return 0;
}//确认边连通
for(int i=0;i<26;i++)
if(din[i]==dout[i]) cnt++;
if(cnt==26) return 1;
if(cnt!=24) return 0;
bool ok_1 = 0,ok_2 = 0;
for(int i=0;i<26;i++)
if(din[i]-dout[i]==1) ok_1 = 1;
else if(dout[i]-din[i]==1) ok_2 = 1;
return ok_1&&ok_2;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(din,0,sizeof din);
memset(vis,0,sizeof vis);
memset(dout,0,sizeof dout);
for(int i=0;i<26;i++) p[i] = i;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
int len =strlen(s+1);
dout[s[1]-‘a‘]++,din[s[len]-‘a‘]++;
vis[s[1]-‘a‘] = vis[s[len]-‘a‘] = 1;
p[findf(s[1]-‘a‘)] = findf(s[len]-‘a‘);
}
if(check()) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
return 0;
}