练习专区

今天的一小步就是明天的一大步
Problem 1462 有向图的可达矩阵………………数构
Accepted: 4   Total Submit: 8
Time Limit: 1000ms   Memory Limit: 30720KB
Description
给你有向图的可达矩阵的定义如下: 现在给你有向图G的边的信息,请你编程求出该图的可达矩阵。假设顶点的编号从1开始。
Input
输入有若干个案例。每个案例的第一行是两个整数m、n表示图中有n个顶点、m条边(0、0表示结束),接着有m行,每行两个整数i、j。表示有从i到j的一条边。
Output
每个案例先输出一行“Case id:”id表示案例的序号,然后输出图可达矩阵。
Sample Input
8 4
1 1
2 1
2 1
2 3
3 1
4 3
3 4
4 1
4 5
1 2
2 3
3 4
3 5
0 0
Sample Output
Case 1:
1 0 0 0
1 1 1 1
1 0 1 1
1 0 1 1
Case 2:
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 0
0 0 0 0 1
Hint
提交     返回