【图论】链式前向星

该算法学习来自 b站

示例代码 1

输出的访问顺序与输入相反

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int n,u,v,w,tot;
struct node{
	int to;
	int nxt;
	int val;
}edge[MS];
int head[MS];

void init(){
	memset(head,-1,sizeof head);
}

void add(int u,int v,int w){
	edge[tot].to = v;
	edge[tot].val = w;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}

void input(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
}

void output(){
	for(int i=0;i<MS;i++){
		for(int j=head[i];j!=-1;j=edge[j].nxt){
			cout << i << "->" << edge[j].to << ":" << edge[j].val << endl;
		}
	}
}

int main() {
	init(); 
	input();
	output();
	
	return 0; 
}

/*
intput:
5
1 2 2 
1 3 4  
2 3 8  
4 5 6 
8 9 3 

output:
1->3:4
1->2:2
2->3:8
2->1:2
3->2:8
3->1:4
4->5:6
5->4:6
8->9:3
9->8:3
*/

示例代码 2

感觉用 vector 更加好理解 ,虽然不是链式前向星了 ,但是代码简单 ,其输出访问顺序与输入相同 .

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 10
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int n,u,v,w;
int val[MS][MS]; 
vector<int> mp[MS];

void input(){
	for(int i=0;i<n;i++){
		cin >> u >> v >> w;
		val[u][v] = val[v][u] = w;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
}

void output(){
	for(int i=0;i<10;i++){
		for(auto &it:mp[i]){
			cout << i << "->" << it << ":" << val[i][it] << endl;
		}
	}
}

int main() {
	cin >> n;
	input();
	output();
	
	return 0; 
}

/*
intput:
5
1 2 2 
1 3 4  
2 3 8  
4 5 6 
8 9 3

output:
1->2:2
1->3:4
2->1:2
2->3:8
3->1:4
3->2:8
4->5:6
5->4:6
8->9:3
9->8:3
*/