彩色的木棒

news/2024/3/29 18:16:14/文章来源:https://blog.csdn.net/chengqiuming/article/details/127252094

一 问题描述

给你一堆木棒。每根棒的每个端点都用一些颜色着色。是否可以将棒对齐成直线,使得接触的端点的颜色具有相同的颜色?

二 输入和输出

1 输入

输入是一系列行,每行包含两个单词,由空格分隔,给出一个木棒的端点颜色。单词是一个不超过 10 个字符的小写字母序列。不超过 250000 根木棒。

2 输出

如果木棒可以以所需方式对齐,则输出单行表示可能,否则输出不可能。

三 输入和输出样例

1 输入样例

blue red

red violet

cyan blue

blue magenta

magenta cyan

2 输出样例

Possible

四 分析和设计

1 分析

本问题可以把木棒的两端看成点,把木棒看成边,相同的颜色为同一个节点。那么问题转化为“一笔画”,即欧拉通路问题,经过每个顶点一次且只有一次,行遍所有的边。

由图论知识可知,无向图存在欧拉通路的充要条件为:

a 图是连通的。

b 无奇度节点或恰好有两个奇度节点(度为奇数的节点)。

连通性可以采用并查集处理,节点的度可以采用字典树进行统计。

解决方案:字典树 + 并查集 + 欧拉通路。

2 设计

a 将输入数据插入到字典树中,并累加颜色节点的度,合并集合。

b 求 1 号节点的集合号(如果连通,则所有节点的集合号相同)。

c 统计奇度节点的个数,如果大于2,则不可能存在欧拉通路,输出不可能。

d 如果集合号不等,则说明不连通,输出不可能。

e 如果没有奇度节点或恰好两个奇度节点,输出可能。

五 代码

package com.platform.modules.alg.alglib.poj2513;public class Poj2513 {private int maxn = 500010;private int maxz = 26; // 不同字符个数,小写字母 26int trie[][] = new int[maxn][maxz];boolean end[];int tot; // 字符串数,下标int color = 0; //颜色编号指针,最终为颜色总个数int degree[];int col[]; // 结点的度数,颜色号int fa[]; // 祖先,即集合号public String output = "";void Init() {end = new boolean[maxn]; // 标记结束degree = new int[maxn];col = new int[maxn];fa = new int[maxn];tot = 1;}// 找祖先int Find(int x) {if (fa[x] != x)fa[x] = Find(fa[x]);return fa[x];}// 合并集合void Union(int a, int b) {int pa = Find(a);int pb = Find(b);fa[pb] = pa;}int Insert(String s) {//将字符串 s 插入到字典树中int p = 1;for (int i = 0; i < s.length(); i++) {int ch = s.charAt(i) - 'a'; // 转换成数字if (trie[p][ch] == 0)trie[p][ch] = ++tot; // 记录下标p = trie[p][ch];}if (end[p]) // 颜色单词已存在return col[p];  //返回其颜色号else { // 否则创建单词end[p] = true;col[p] = ++color;return col[p];}}public String cal(String input) {Init();for (int i = 1; i < maxn; i++)fa[i] = i;String[] line = input.split("\n");for (int k = 0; k < line.length; k++) {String[] colors = line[0].split(" ");int i = Insert(colors[0]);int j = Insert(colors[1]); // 得到 a、b 颜色的编号degree[i]++;degree[j]++;// 记录 a、b 颜色出现的次数(总度数)Union(i, j);}int s = Find(1); // 若图为连通图,则 s 为所有结点的祖先int num = 0;  // 度数为奇数的结点个数for (int i = 1; i <= color; i++) {if (degree[i] % 2 == 1)num++;if (num > 2 || Find(i) != s) { // 存在多个祖先,图为森林,不连通output = "Impossible\n";return output;}}if (num == 0 || num == 2) // 没有奇度顶点或恰好两个奇度顶点output = "Possible\n";elseoutput = "Impossible\n";return output;}
}

六 测试

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_398754.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SkeyeVSS智慧国土高点视频监控解决方案

随着经济的快速发展、城镇化的快速推进&#xff0c;耕地及矿产资源等不断减少&#xff0c;未批先建、批少用多、私自改变土地用途等各种违法违规用地行为时有发生&#xff0c;在这种情况下&#xff0c;传统的人力巡查工作效率低、执法成本高的弊端进一步凸显。 SkeyeVSS智慧国土…

科技云报道:私有云市场加速洗牌,超云为何异军突起?

科技云报道原创。 近年来在国家相关政策的大力推动下&#xff0c;中国私有云市场发展渐入佳境&#xff0c;一股新的建设高潮汹涌而至。 根据IDC对于2022-2026中国SDS及HCI的市场预测&#xff0c;中国私有云基础架构市场正在从成长阶段迈向成熟阶段&#xff0c;未来3-5年将保持…

自己动手写ls命令——Java版

自己动手写ls命令——Java版 介绍 在前面的文章Linux命令系列之ls——原来最简单的ls这么复杂当中&#xff0c;我们仔细的介绍了关于ls命令的使用和输出结果&#xff0c;在本篇文章当中我们用Java代码自己实现ls命令&#xff0c;更加深入的了解ls命令。 代码实现 文件操作的…

3000字神经网络论文

你遇到了哪些困难和挫折是怎样克服的写下来的作文 我学会了骑自行车人生的道路上&#xff0c;谁都会遇到困难或挫折&#xff0c;就看你敢不敢去挑战它。那一次学自行车&#xff0c;一直让我记忆犹新。一天傍晚&#xff0c;我和爸爸妈妈一起推着车来到体育馆&#xff0c;这次我…

Android同文输入法的使用(开源输入法Trime)

Trime输入法背景源码APP试用下载安装配置部署成功后再一步&#xff1a;学习如何 DIY总结背景 想找一款开源的Android中文输入法&#xff0c;然后发现了这款备受推崇的输入法框架rime。 RIME&#xff0f;中州韵输入法引擎&#xff0c;是一个跨平台的输入法算法框架。 基于这一…

【MySQL】检索数据

每日鸡汤 &#xff1a; —— 若你困于无风之地&#xff0c;我将奏响高空之歌 要和我一起花 10 min 学一会 SQL 嘛&#xff1f; - 当然愿意&#xff0c;我美丽的小姐 &#xff08;封寝期间练就的自言自语能力越来越炉火纯青了~~~&#xff09; 前言&#xff1a; 本实验中所用数据…

Kotlin第二章:kotlin基础

1. 基础数据类型 1. 整数类型 序号类型位宽最小值最大值1Byte8-1281272Short16-32768327673Int32-2,147,483,648 (-2^31)2,147,483,647 (2^31 - 1)4Long64-9,223,372,036,854,775,808 (-2^63)9,223,372,036,854,775,807 (2^63 - 1) val number 100 //默认Int类型 类比java的…

0050 Enum枚举类

/* 枚举是一种特殊的类&#xff0c;里面只包含一组有限的特定对象枚举的两种实现方式1.自定义类实现枚举2.使用enum关键字实现枚举自定义类实现枚举1.构造器私有化2.本类的内部创建一组对象[]3.对外暴露对象&#xff08;为对象添加public final static修饰&#xff09;4.提供g…

第三章 Flink基础理论之内存优化及常见内存报错解决方案

第三章 Flink基础理论之内存优化及常见内存报错解决方案 哇. 1、总体内存模型 1.1、内存模型概述 ​ Flink内存配置分为JobManager内存配置和TaskManager内存配置。 配置项TaskManager配置参数JobManager配置参数Total Flink Memorytaskmanager.memory.flink.sizejobmana…

土方量计算的准确作法

​现在说到土方量结算&#xff0c;绝大多数土木行业的人都说某某软件很方便&#xff0c;但是我要问到手算会吗&#xff0c;大多数人都会支支吾吾&#xff0c;虽然手算确实不现实&#xff0c;但是我们做为专业人员&#xff0c;总不能沦为软件使用者吧&#xff1f;其中的原理大家…

公众号网课题库系统-注册即可使用

公众号网课题库系统-注册即可使用 本平台优点&#xff1a; 多题库查题、独立后台、响应速度快、全网平台可查、功能最全&#xff01; 1.想要给自己的公众号获得查题接口&#xff0c;只需要两步&#xff01; 2.题库&#xff1a; 题库&#xff1a;题库后台&#xff08;点击跳转…

大数据专题-spark mysql python爬虫携程景点爬取(含虚拟机镜像)

博主介绍&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域✌ 项目名称 大数据专题-spark mysql python爬虫携程景点爬取&#xff08;含虚拟机镜像&#xff09; 视频效果 大数据专题-spark mysql python爬虫携程景点系统说明 一&…

Vue组件之间的数据共享详解

目录前言一&#xff0c;props的作用二&#xff0c;父向子传值2.1 子元素2.2 父元素2.3 整体代码三&#xff0c;子向父传值3.1 子组件3.2 父组件3.3 整体代码四&#xff0c;兄弟之间的数据传递4.1 事件总线EventBus介绍(面试高频&#xff09;4.2 传值方4.3 接收方后记前言 组件…

Servlet - Filtering (过滤器))

[TOC](Servlet - Filtering (过滤器) ) 1. What 1.1 什么是Filter Servlet过滤器Filter是一个小型的web组件&#xff0c;它们通过拦截请求和响应&#xff0c;以便查看、提取或以某种方式操作客户端和服务器之间交换的数据&#xff0c;实现“过滤”的功能。Filter通常封装了一…

深度神经网络的优化算法,进化算法优化神经网络

有哪些手段可以提升深度神经网络的泛化性能 人工神经网络以其智能性见长&#xff0c;那么神经网络能真的学到一个映射的本质吗&#xff1f;也就是说&#xff0c;对一个映射给出一定的必要的训练样本训练后&#xff0c;网络能否对样本以外的样本给出较为准确的预测。 泛化能力…

概率论与数理统计学习:随机向量(三)——知识总结与C语言实现案例

hello&#xff0c;大家好 这里是第八期概率论与数理统计的学习&#xff0c;我将用这篇博客去总结这期的知识点以及实现用C语言去做题的过程。 本期知识点&#xff1a; 条件分布 条件分布的概念离散型随机变量的条件概率分布连续型随机变量的条件概率密度 随机变量的独立性 那…

ROS学习笔记三(TF的类)

1.数据类型 数据类型定义在tf/transform_datatypes.h.里 1.1 基本数据类型(Quaternion, Vector, Point, Pose, Transform) TypetfQuaterniontf::QuaternionVectortf::Vector3Pointtf::PointPosetf::PoseTransformtf::Transform 1.2 tf::Stamped tf::Stamped在上面的数据类型…

RocketMQ 5.0:无状态代理模式的探索与实践

本文作者&#xff1a;金吉祥&#xff0c; Apache RocketMQ PMC Member&#xff0c;阿里云智能高级技术专家 背景 首先&#xff0c;让我们来看下是遇到了哪些痛点问题&#xff0c;促使我们去探索一种无状态代理的RocketMQ新架构的&#xff1b; RocketMQ 拥有一套极简的架构&am…

安卓投屏 QtScrcpy

一、电脑安装adb 版本大于1.0.40以上 40不行 adb 1.0.41下载链接 链接&#xff1a;https://pan.baidu.com/s/1WIPI-p7a4ErTLFYHaTC2kw?pwdadbt 提取码&#xff1a;adbt 安装参考 https://blog.csdn.net/M7_xbc/article/details/122957311 二、打开无线调试并且配对 手机打…

驱动开发(10/10-林雪阵)

终端输入1--->LED1点亮 终端输入2--->LED2点亮 终端输入3--->LED3点亮 终端输入0--->LED熄灭 chdev.c (底层驱动代码&#xff09; #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include <linux/uaccess.h>…