数据结构基础

【题目描述】

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

例如有一个图结点有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)