链式先前星 存储图的信息

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <set>
 5 #include <fstream>
 6 using namespace std;
 7 const int maxn=1100000;
 8 const int maxm=110000;
 9 
10 using namespace std;
11 
12 struct Edge//边的的数组
13 {
14     int next, n, to;//分别代表下一个 相同起点的位置 这条边的权值 这条边的终点
15 }edge[maxm];//所有的边都将储存在这个数组当中
16 
17 int head[maxn];// head[i] 表示从i点出发的 边的第一个节点 在edge数组中的位置
18 
19 int num = 0; //当前已有边的个数
20 
21 int Add(int from, int to, int n)//分别代表的信息 :从哪个点出发 终点 权值
22 {
23     edge[num].n = n;
24     edge[num].to = to;
25     edge[num].next = head[from];//从头插入
26     head[from] = num++;//更新头节点
27 }
28 
29 void use(int v)//遍历以v为起点的链表---->> 输出所有以v为起点的边
30 {
31     int t = head[v];
32     while (t != -1)//head 和 edge初始化为-1
33     {
34         cout << v << " ----> " << edge[t].to << " : " << edge[t].n << endl;
35         t = edge[t].next;
36     }
37 }
38 
39 
40 int main()
41 {
42     ifstream cin ("in.txt");
43     int from[128], to[128], n[128];
44     int i = 0;
45     memset(edge, -1, sizeof(edge));
46     memset(head, -1, sizeof(head));
47     while (cin >> from[i] >> to[i] >> n[i])
48     {
49         Add(from[i], to[i], n[i]);
50         i++;
51     }
52     //下面测试就是在乱搞了
53     set<int> s;
54     set<int> :: iterator it;
55     for (int j = 0; j < i; j++)
56     {
57         s.insert(from[j]);//去重
58     }
59     for(it = s.begin(); it != s.end(); it++)
60     {
61         use((*it));
62     }
63 }

测试输入
1 3 2
1 2 5
2 3 4
2 4 2
4 3 6
4 6 1
3 5 10
5 6 3
5 7 5
6 9 7

输出
1 ----> 2 : 5
1 ----> 3 : 2
2 ----> 4 : 2
2 ----> 3 : 4
3 ----> 5 : 10
4 ----> 6 : 1
4 ----> 3 : 6
5 ----> 7 : 5
5 ----> 6 : 3
6 ----> 9 : 7