ACM-ICPC-OJ训练营

问题 3173 --离散数学

3173: 离散数学

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 31
[提交][状态][讨论版][命题人:]

题目描述

在离散数学课上，老师在讲关系的性质的传递性时。小劉同学不认真听讲，导致他不会判断什么是传递性。并且可怕的是他的老师给他布置了一个作业，这个作业的内容是一个集合A有x个数，分别是从1到x。有n个序偶（即数对），这些序偶都是R在A上的关系并且序偶中的数均小于等于x，现在需要判断R是否具有传递性，小劉不会做，请你帮助小劉同学解开它。

输入描述

第一行一个整数t，表示有t组样例（1<=t<=100）
每一个样例中第一行一个整数n和x，n表示有n个序偶，x表示在集合A有从1到x的每个元素（3<=n<=x*x, 2<=x<=10）

输出描述

每一个样例输出一行，有传递性输出"Yes"，反之则输出"No"

样例输入

样例输出

Yes

提示

鉴于一些同学也像小劉一样上课不认真听讲，也不会传递性的定义，所以现在给出传递性的定义：A是一个集合，R是A上的关系，若<x,y>∈R，且<y,z>∈R,则<x,z>∈R.

即R={<1,2>,<2,1>,<1,1>,<2,2>},在这个关系中

<1,2>和<2,1>能够推出<1,1>;

<2,1>和 <1,2>能推出<2,2>；

<1,1>和<1,2>能推出<1,2>;

<2,2>和<2,1>能推出<2,1>；

<1,1>，<2,2>，<1,2>，<2,1>都存在R中，R即拥有传递性.

这要是再看不懂，就等着离散挂科吧

来源

23软3刘震峰

[提交][状态]