AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 1185. 单词游戏

作者: 作者的头像   wyc1996 ,  2020-12-16 20:06:04 ,  阅读 19


1


#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=30;
int n;
int din[N],dout[N],p[N];
bool st[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin>>T;
    char str[1010];
    while(T--){
        scanf("%d",&n);
        memset(din,0,sizeof din);
        memset(dout,0,sizeof dout);
        memset(st,0,sizeof st);
        for(int i=0;i<26;i++)p[i]=i;

        for(int i=0;i<n;i++){
            scanf("%s",str);
            int len=strlen(str);
            int a=str[0]-'a',b=str[len-1]-'a';
            st[a]=st[b]=true;
            dout[a]++,din[b]++;
            p[find(a)]=find(b);
        }

        int start=0,end=0;
        bool success=true;
        for(int i=0;i<26;i++){
            if(din[i]!=dout[i]){
                if(din[i]==dout[i]+1)end++;
                else if(din[i]+1==dout[i])start++;
                else {
                    success=false;
                    break;
                }
            }
        }
        if(success && !(!start && !end || start==1 &&end==1))success=false;

        int rep=-1;
        for(int i=0;i<26;i++){
            if(st[i]){
                if(rep==-1)rep=find(i);
                else if(rep!=find(i)){
                    success=false;
                    break;
                }
            }
        }
        if(success)puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    return 0;
}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息