CODEVS 1019 集合论与图论

题目描述 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;

#include <cstdio>
#include <cstring>

bool graph[1001][1001];

int main(){
	int t,n,m,a,b;
	bool trans = true;
	scanf("%d",&t);
	for(int i = 0;i < t;i++){
		trans = true;
		scanf("%d%d",&n,&m);
		memset(graph,0,sizeof(graph));
		for(int j = 0;j < m;j++){
			scanf("%d%d",&a,&b);
			graph[a][b] = true;
		}
		for(int x = 1;x <= n;x++)
			for(int y = 1;y <= n;y++)
				if(graph[x][y] && x!=y)
					for(int z = 1;z <= n;z++)
						if(graph[y][z])
							if(!graph[x][z]){
								trans = false;
								break;
							}
		if(trans)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

此条目发表在CODEVS分类目录。将固定链接加入收藏夹。