acwing1185. 单词游戏(欧拉图)「建议收藏」

acwing1185. 单词游戏(欧拉图)「建议收藏」有 N 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。输入格式第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含整数 N,表示盘子数量。接下来 N 行,每行包含一个小写字母字符串,表示一个盘子上的单词。一个单词可能出现多次。输出格式如果存在合法解,则输出”Ordering is possible.”,否则输出”The

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

有 N 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序,判断是否能达到这一要求。

输入格式
第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含整数 N,表示盘子数量。

接下来 N 行,每行包含一个小写字母字符串,表示一个盘子上的单词。

一个单词可能出现多次。

输出格式
如果存在合法解,则输出”Ordering is possible.”,否则输出”The door cannot be opened.”。

数据范围
1≤N≤105,
单词长度均不超过1000

输入样例:
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
输出样例:
The door cannot be opened.
Ordering is possible.
The door cannot be opened.

题解
欧拉回路

#include<bits/stdc++.h>
using namespace std;
const int N = 26;
int f[N],in[N],out[N],vis[N];
int find(int x){ 
   
    return f[x] = (x == f[x] ? f[x] : find(f[x]));
}

int main(){ 
   
    int T;
    scanf("%d",&T);
    int n;
    while(T --){ 
   
        memset(in,0,sizeof in);
        memset(out,0,sizeof out);
        memset(vis,0,sizeof vis);
        for(int i = 0;i < 26;i ++)f[i] = i;
        scanf("%d",&n);
        char s[1010];
        while(n --){ 
   
            scanf("%s",s);
            int a = s[0] - 'a',b = s[strlen(s) - 1] - 'a';
            in[b] ++ ,out[a] ++;
            f[find(a)] = find(b);
            vis[a] = vis[b] = true;
        }
        int l = 0,h = 0;
        bool f = true;
        for(int i = 0;i < 26;i ++){ 
   
            if(in[i] != out[i]){ 
   
                if(in[i] == out[i] + 1)l ++;
                else if(in[i] == out[i] - 1)h ++;
                else f = false;
            }
        }
        if(f && ((l != 1 || h != 1) && !(l == 0 && h == 0)))f = false;
        int p = -1;
        for(int i = 0;i < 26;i ++){ 
   
            if(vis[i]){ 
   
                if(p == -1)p = find(i);
                else if(find(i) != p){ 
   
                    f = false;
                    break;
                }
            }
        }
        if(!f)cout<<"The door cannot be opened."<<endl;
        else cout<<"Ordering is possible."<<endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168588.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 联想笔记本电脑键盘灯怎么开启_联想键盘灯怎么开

    大家好,我是时间财富网智能客服时间君,上述问题将由我为大家进行解答。联想笔记本键盘灯的打开方法如下:1、正常情况下,在键盘上同时按下“FN”和“空格”键打开即可。2、部分早期的Thinkpad笔记本电脑需要通过“Fn+PageUp”组合键开启。如果电脑键盘的“Space(空格键)”按键上有类似太阳的标识符号,电脑一般带有键盘背光,使用“Fn+Space(空格键)”组合键即可开启键盘背光。若“Sp…

  • maven 本地仓库配置_maven默认的本地仓库

    maven 本地仓库配置_maven默认的本地仓库一、maven配置本地仓库路径1.打开安装好的maven目录2.进入conf–>编辑settings.xml文件3.修改<localRepository>找到并修改<localRepository>,最初是注释掉的,取消注释就可以 <localRepository>你想存放的本地仓库路径</localRepository>(不修改默认${user.home}/.m2/repository这个路径)二、配置中央仓库我这里用的阿里

  • IntelliJ Idea — 多次启动同一个main 方法[通俗易懂]

    IntelliJ Idea — 多次启动同一个main 方法[通俗易懂]第一次启动后面会出现启动记录,进入配页需要多次启动main打上勾这样就可以无限制的启动了

  • R语言入门mac——RStudio安装➕R包安装【附安装链接】[通俗易懂]

    R语言入门mac——RStudio安装➕R包安装【附安装链接】[通俗易懂]R语言入门mac——安装【附安装链接】这里写目录标题R语言入门mac——安装【附安装链接】一、总体安装步骤1安装R2下载RStudio二、R包安装一、总体安装步骤1安装RRStudio需要R3.0.1+下载链接:https://cran.rstudio.com/2下载RStudio下载链接:https://rstudio.com/products/rstudio/download/二、R包安装下面展示r包安装代码rm(list=ls())options()$repos

  • 微信集赞作弊_朋友圈分享集赞是非法行为吗

    微信集赞作弊_朋友圈分享集赞是非法行为吗从古至今,无论是征战沙场的猛将,还是心怀天下的文豪,抑或探索人生真理的大哲学家,都将“独立、自由”等当做人之所以为人的奋斗目标和根本标准。但可惜的是,无论是外来环境、文化的影响,还是内在的个人成长过程,都缺乏对“独立、自由”的尊重和支撑。而在当下的移动互联网时代,以微信为代表的社交应用,更是在某种程度上扼杀着大众的独立和自由。虽然这并不是微信有意去做…

  • Eurake[通俗易懂]

    Eurake[通俗易懂]eureka-core模块包含了功能的核心实现:1.com.netflix.eureka.cluster-与peer节点复制(replication)相关的功能2.com.netflix.eureka.lease-即”租约”,用来控制注册信息的生命周期(添加、清除、续约)3.com.netflix.eureka.registry-存储、查询服务注册信息4.com.n…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号