拓扑排序-jobdu-1448

简介:  题目1448:Legal or Not 题目描述:ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT,

 题目1448:Legal or Not

题目描述:
ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not. Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.
输入:
The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0.TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.
输出:
For each test case, print in one line the judgement of the messy relationship.If it is legal, output "YES", otherwise "NO".
样例输入:
3 2
0 1
1 2
2 2
0 1
1 0
0 0
样例输出:
YES
NO
  微笑大意:master 师傅、prentice 徒弟
一个qq群,一些人之间存在师徒关系,该关系是传递的。让判断是否有两人,存在既是师徒,又是徒弟跟师傅这样的非法关系。
分析:用拓扑排序来解决。每人看做一个点,a是b的师傅,则用相应有向弧存储。
目录
相关文章
|
API 网络架构 索引
Elasticsearch索引中数据的增删改查与并发控制
Elasticsearch索引中数据的增删改查与并发控制
126 0
|
7月前
|
算法 安全 开发者
优化if-else的11种方案
优化if-else结构的方法多种多样,通过选择合适的方法,可以提高代码的可读性、可维护性和灵活性。本文详细介绍了11种优化if-else的方法,并通过代码示例说明了每种方法的具体应用。希望这些方法能够帮助开发者在实际编程
289 21
|
9月前
|
Shell Linux Ruby
Python3虚拟环境venv
`venv` 是 Python 的虚拟环境工具,用于为不同项目创建独立的运行环境,避免依赖冲突。通过 `python3 -m venv` 命令创建虚拟环境,并使用 `source bin/activate` 激活。激活后,所有 Python 包将安装在该环境中,不影响系统全局环境。退出环境使用 `deactivate` 命令。每个虚拟环境拥有独立的包集合,确保项目间的隔离性。删除虚拟环境只需删除其目录即可。
542 34
|
机器学习/深度学习 安全 算法
【2023年第十一届泰迪杯数据挖掘挑战赛】A题:新冠疫情防控数据的分析 建模方案及python代码详解
本文介绍了2023年第十一届泰迪杯数据挖掘挑战赛A题的解题思路和Python代码实现,涵盖了新冠疫情防控数据的分析、建模方案以及数据治理的具体工作。
263 0
【2023年第十一届泰迪杯数据挖掘挑战赛】A题:新冠疫情防控数据的分析 建模方案及python代码详解
|
11月前
|
IDE Java 开发工具
移动应用与系统:探索Android开发之旅
在这篇文章中,我们将深入探讨Android开发的各个方面,从基础知识到高级技术。我们将通过代码示例和案例分析,帮助读者更好地理解和掌握Android开发。无论你是初学者还是有经验的开发者,这篇文章都将为你提供有价值的信息和技巧。让我们一起开启Android开发的旅程吧!
|
Ubuntu Linux 数据安全/隐私保护
使用Cython库包对python的py文件(源码)进行加密,把python的.py文件生成.so文件并调用
本文介绍了在Linux系统(Ubuntu 18.04)下将Python源代码(`.py文件`)加密为`.so文件`的方法。首先安装必要的工具如`python3-dev`、`gcc`和`Cython`。然后通过`setup.py`脚本使用Cython将`.py文件`转化为`.so文件`,从而实现源代码的加密保护。文中详细描述了从编写源代码到生成及调用`.so文件`的具体步骤。此方法相较于转化为`.pyc文件`提供了更高的安全性。
1074 2
|
机器学习/深度学习 传感器 人工智能
毫末智行艾锐谈自动驾驶大模型:全新范式是「生存」必选项
毫末智行艾锐谈自动驾驶大模型:全新范式是「生存」必选项
561 0
|
人工智能 自动驾驶 安全
科技公司反内卷的典型样本
互联网整个行业都在陷入被动且尴尬的局面。去年开始流行的“内卷”一词,恰如其分的描述了互联网的现状,比如抖音开始做外卖,微信强推视频号,一直硝烟弥漫的电商市场,更是激战在社区团购上。内卷背后也有人感慨,互联网到了尽头。支撑这一论述的是,移动互联网的人口红利已经消失,几款国民型APP用户增长都固定在了10亿这个级别,只能依靠自然人口的增长和迁移。
|
Shell 开发工具 数据安全/隐私保护
idea配置多个git/github账户
首先拉取项目到本地:
1513 0
|
监控 前端开发
29分布式电商项目 - 商品录入(三级联动菜单)
29分布式电商项目 - 商品录入(三级联动菜单)
103 0