前向星表示法

Grade 100 Open Time Friday, 24 July 2020, 8:40 AM
Discount 0.8 Time Discount Friday, 24 July 2020, 8:40 AM
Allow late Yes Close Time Friday, 24 July 2020, 8:40 AM
Input file star.in Output file star.out

【题目描述】

在做图的题目时,经常会遇到图很大,边很少的情况,如果用矩阵存图,空间复杂度就会过大,这时可以用前向星方式存储数据。

例如有一个图结点有100 000个,普通的矩阵存图空间即是100 000×100 000。而前向星是保存边,比如说第i条边(u,v)=w,就分别把起点、终点、权值存在u[i]、v[i]和w[i]三个数组中(下标相同)。

前向星是一种星形表示法,星形表示法分为前向星和后向星。前向星按照起始结点从小到大排序,前向星的好处是比链表节省时间和空间,只要不增加或者删除边,就能很快找到从一个点出发的所有边。除了不能直接用起点终点定位以外,前向星几乎是完美的。

例如图5个顶点7条边:

程序运行时输入:

5 7

1 2 10

2 5 11

3 1 14

3 2 15

4 3 13

4 2 16

5 4 12

则结果为:

1->2(10)

2->5(11)

3->2(15)->1(14)

4->2(16)->3(13)

5->4(12)

【输入样例】

5 7

1 2 10

2 5 11

3 1 14

3 2 15

4 3 13

4 2 16

5 4 12

【输出样例】

1->2(10)

2->5(11)

3->2(15)->1(14)

4->2(16)->3(13)

5->4(12)