离散题目18
Time Limit: 1000MS
Memory Limit: 65536KB
Submit
Statistic
Problem Description
给出一个集合A和A上的关系R,求关系R的传递闭包。
例如:
A={0,1,2} , R={<0,0>,<1,0>,<2,2>,<1,2>,<2,1>}
t(R) = {<0,0>,<1,0>,<2,2>,<2,1>,<1,2>,<1,1>,<2,0>};
Input
多组输入,输入n、m,集合A={0, 1, …, n-1 };m代表关系的数量,n、m不超过20.
Output
每组输入输出t(R),根据t(R)中序偶的第一个数字升序排序,如果第一个数字相同,根据第二个升序排序。
Example Input
Example Output
0 0
1 0
1 1
1 2
2 0
2 1
2 2
think:可以直接用三层for解决,因为数据量不是很大,所以不会超时;
代码:
#include <bits/stdc++.h>
using namespace std;
int a[25][25];
int main()
{
int k, i, j, x, y, n, m;
while(~scanf("%d%d", &n, &m))
{
memset(a, 0, sizeof(a));
for(i = 0;i < m;i++)
{
scanf("%d%d", &x, &y);
a[x][y] = 1;
}
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
if(a[j][i] == 1)
{
for(k = 0;k < n;k++)
{
if(a[i][k] == 1)
a[j][k] = 1;
}
}
}
}
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
if(a[i][j] == 1)
printf("%d %d\n", i, j);
}
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)