利用vector建立邻接表

1. 对于无权图：

1 #include<algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cstdio> 7 #include <vector> 8 #include <queue> 9 #include <cmath> 10 using namespace std; 11 const int MAXM = 200000 + 10; 12 13 int n, m; 14 vector<int> p[MAXM]; 15 16 inline void add(int u, int v) { 17 p[u].push_back(v); 18 p[v].push_back(u); // 有向图删掉本行 19 } 20 21 int main() { 22 cin >> n >> m; 23 for(int i=1; i<=m; ++i) { 24 int x, y; 25 scanf("%d%d", &x, &y); 26 add(x, y)； 27 } 28 return 0; 29 }

 

2. 对于有权图：

1 #include<algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cstdio> 7 #include <vector> 8 #include <queue> 9 #include <cmath> 10 using namespace std; 11 const int MAXM = 200000 + 10; 12 13 struct Edge { int to, val; }; 14 15 int n, m; 16 vector<Edge> p[MAXM]; 17 18 inline void add(int u, int v, int w) { 19 Edge temp; 20 temp.to = v; 21 temp.val = w; 22 p[u].push_back(temp); 23 temp.to = u; // 有向图删掉以下两行 24 p[v].push_back(temp); 25 } 26 27 int main() { 28 cin >> n >> m; 29 for(int i=1; i<=m; ++i) { 30 int x, y, w; 31 scanf("%d%d%d", &x, &y, &w); 32 add(x, y, w); 33 } 34 return 0; 35 }

 

转载于:https://www.cnblogs.com/Marginalin/p/9875217.html