在学会邻接矩阵之后, 我等渣渣算是了解了一种图的储存方式, 但是邻接矩阵有着一个缺点, 那就是不适合存稀疏图 (时空复杂度均为 n^2), 否则会爆 Memory, 然后你就会收到一个长得真不怎么好看的 MLE. 这个时候邻接表就来了, 简单理解的话就是用单链表来表示图.
有向无权图
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pb push_back
- #define fio ios::sync_with_stdio(false);cin.tie(0);
- #define pii pair<int,int>
- #define vi vector<int>
- #define vc vector<char>
- #define pi 3.1415926
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- const int INF=0x3f3f3f3f;
- const int N=2e5+5;
- typedef long long ll;
- typedef double db;
- typedef unsigned long long ull;
- using namespace std;
- vi Graph[N];
- int main()
- {
- fio;
- int n,m;//n 个点, m 组数据
- cin>>n>>m;
- int start,to;
- for (int i=1;i<=m;i++)
- {
- cin>>start>>to;
- Graph[start].pb(to);// 有向无权图
- }
- }
无向无权图
- int main()
- {
- fio;
- int n,m;//n 个点, m 组数据
- cin>>n>>m;
- int start,to;
- for (int i=1;i<=m;i++)
- {
- cin>>start>>to;
- Graph[start].pb(to);
- Graph[to].pb(start);
- }
- }
有向有权图
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pb push_back
- #define fio ios::sync_with_stdio(false);cin.tie(0);
- #define pii pair<int,int>
- #define vi vector<int>
- #define vc vector<char>
- #define pi 3.1415926
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- const int INF=0x3f3f3f3f;
- const int N=2e5+5;
- typedef long long ll;
- typedef double db;
- typedef unsigned long long ull;
- using namespace std;
- struct node
- {
- int to;
- int value;
- };
- vector<node> Graph[N];
- int main()
- {
- fio;
- int n,m;//n 个点, m 组数据
- cin>>n>>m;
- int start,to;
- for (int i=1;i<=m;i++)
- {
- node temp;
- cin>>start>>temp.to>>temp.value;
- Graph[start].pb(temp);
- }
- }
有向无权图
- struct node
- {
- int to;
- int value;
- };
- vector<node> Graph[N];
- int main()
- {
- fio;
- int n,m;//n 个点, m 组数据
- cin>>n>>m;
- int start,to;
- for (int i=1;i<=m;i++)
- {
- node temp;
- cin>>start>>temp.to>>temp.value;
- Graph[start].pb(temp);
- swap(start,temp.to);
- Graph[start].pb(temp);
- }
- }
来源: http://www.bubuko.com/infodetail-2685204.html