专栏首页数据结构与算法1019 集合论与图论

1019 集合论与图论

1019 集合论与图论

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

       集合论与图论对于小松来说是比数字逻辑轻松,比数据结构难的一门专业必修课。虽然小松在高中的时候已经自学过了离散数学中的图论,组合,群论等知识。但对于集合论,小松还是比较陌生的。集合论的好多东西也涉及到了图论的知识。

       在第四讲的学习中,小松学到了“有序对”这么一个概念,即用<x, y>表示有序对x和y。要注意的是有序对<x, y>不等于有序对<y, x>。对于一个有序对集合R={<x,y>, <y, z>, <x,  z>,……},我们说R是传递的,当且仅当他满足下面的性质:

红色字体用直观的语言描述是:如果存在<x, y>∈R,<y, z>∈R,那么一定存在<x, z>∈R。

       这里集合R可以对应到一个有向图G,有序对<x ,y>对应到了G中的一条有向边。 你现在的任务是,对于任意给定的一个简单有向图G(同一有向边不出现两次),判断G是否具有传递性。

输入描述 Input Description

       输入文件set.in第一行包含测试数据的个数T(1<=T<=10)。接下来T组测试数据,每组测试数据第一行包含两个个整数n和m(1<=n<=1000, n<=m<=100000),表示G中元素个数和有向边的个数,接下来的m行每行2个整数x, y(1<=x,y<=n)表示x与y之间有一条有向边连接。

输出描述 Output Description

       对于每组数据,如果G是传递的,你需要向输出文件set.out输出一行”Yes”, 否则输出一行”No”。

样例输入 Sample Input

2

3 3

1 2

1 3

2 3

4 5

1 2

1 3

1 4

2 3

3 4

样例输出 Sample Output

Yes

No

数据范围及提示 Data Size & Hint

有30%满足1<=n<=100, 1<=m<=10000;

有100%的数据满足1<=n<=1000, 1<=m<=100000;

分类标签 Tags 点此展开

条件的话题目已经已经说得很清楚了,就是x,y,z之间的关系,而xyz又恰好是三个字母,这样我们用Flyod就可以完美解决了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=1001;
 6 const int maxn=0x7fffffff;
 7 int map[MAXN][MAXN];
 8 int vis[100001];
 9 int x,y,z;
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         memset(map,0,sizeof(map));
17         int n,m;
18         scanf("%d%d",&n,&m);
19         /*for(int i=1;i<=n;i++)
20         for(int j=1;j<=n;j++)
21             map[i][j]=maxn;
22         for(int i=1;i<=n;i++)
23         map[i][i]=0;*/
24         for(int i=1;i<=m;i++)
25         {
26             scanf("%d%d",&x,&y);
27             map[x][y]=1;
28         }
29         int flag=0;
30         for(int x=1;x<=n;x++)
31         {
32             for(int y=1;y<=n;y++)
33             {
34                 if(map[x][y]==1)
35                 for(int z=1;z<=n;z++)
36                 {
37                     /*if(map[i][j]||(map[i][k]&&map[k][j]))
38                     vis[i]=vis[j]=1;*/
39                     if(map[y][z]==1)
40                     {
41                         if(map[x][z]==0)
42                         {
43                             flag=1;
44                             break;
45                         }
46                     }
47                 }
48             }
49         }
50         /*for(int i=1;i<=n;i++)
51         {
52             if(vis[i]==0)
53             {
54                 flag=1;
55                 break;
56             }
57         }*/
58         if(flag==1)
59         {
60             printf("No\n");
61         }
62         else
63         {
64             printf("Yes\n");
65         }
66     }
67     return 0;
68 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1020 孪生蜘蛛

    1020 孪生蜘蛛 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在G城保卫...

    attack
  • 2577 医院设置

    2577 医院设置 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 设有一棵二叉...

    attack
  • 1722 最优乘车 未完成

    1722 最优乘车 1997年NOI全国竞赛  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解 题目描述 Des...

    attack
  • 1020 孪生蜘蛛

    1020 孪生蜘蛛 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在G城保卫...

    attack
  • 1722 最优乘车 未完成

    1722 最优乘车 1997年NOI全国竞赛  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解 题目描述 Des...

    attack
  • 城市公交网建设问题

    【问题描述】   有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点...

    attack
  • 1079 回家

    1079 回家 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 现在是晚餐...

    attack
  • 157. [USACO Nov07] 奶牛跨栏

    157. [USACO Nov07] 奶牛跨栏 ★★   输入文件:hurdles.in   输出文件:hurdles.out 简单对比 时间限制:1 s   ...

    attack
  • 最优布线问题

    【问题描述】   学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同,因此不同的两...

    attack
  • App基于手机壳颜色换肤?先尝试一下用 KMeans 来提取图像中的主色

    上周,某公司的产品经理提了一个需求:根据用户手机壳颜色来改变 App 主题颜色。可能是由于这天马行空的需求激怒了程序员,导致程序员和产品经理打了起来,最后双双被...

    fengzhizi715

扫码关注云+社区

领取腾讯云代金券