莫欺少年穷,修魔之旅在这开始—>算法提高课题解
思路:
1. 有向图:欧拉路径:所有点(除起点和终点)入度等于出度,入度=出度+1(终点),入度+1=出度(起点)
2. 如果是欧拉回路,则所有点入度等于出度
3. 此题只需要把每个单词看成是从首字母向尾字母连一条有向边,判断这些边是否构成欧拉路径即可
4. 用并查集判断边是否连通即可
#include<bits/stdc++.h>
using namespace std;
const int N = 26;
int n;
int din[N],dout[N];
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int T;
cin>>T;
while(T--)
{
//数组初始化
memset(din,0,sizeof din);
memset(dout,0,sizeof dout);
cin>>n;
//并查集初始化
for(int i=0;i<N;i++) p[i]=i;
string str;
while(n--)
{
cin>>str;
//首字母向尾字母连一条有向边
int a=str[0]-'a',b=str[str.size()-1]-'a';
dout[a]++,din[b]++;
p[find(a)]=find(b);
}
int start=0,end=0;
bool flag=true;
for(int i=0;i<N;i++)
if(din[i]!=dout[i])
{
//终点只能有一个
if(din[i]==dout[i]+1) end++;
//起点只能有一个
else if(din[i]+1==dout[i]) start++;
//不符合有向图欧拉路径的条件
else
{
flag=false;
break;
}
}
//判断是否符合有向图欧拉路径的条件
if(flag&&!(!end&&!start||end==1&&start==1)) flag=false;
//判断所有边是否连通
int rep=-1;
for(int i=0;i<N;i++)
if(din[i]) //用 din 即可判断该点是否出现过
{
if(rep==-1) rep=find(i);
//边不连通
else if(rep!=find(i))
{
flag=false;
break;
}
}
if(flag) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
return 0;
}