Self study understanding of [chain forward star]

Let's take the following figure as an example ：

According to the order of edge construction , We can create a sequence number for these edges , Such as ：

1 2      <---1 Number 
2 3      <---2 Number 
3 4      <---3 Number 
1 3      <---4 Number 
4 1      <---5 Number 
1 5      <---6 Number 
4 5      <---7 Number 

according to 《 Algorithm competition 》 Ideas given in , We can write a linked list ：

1 -> 5 -> 3 -> 2
2 -> 3
3 -> 4
4 -> 5 -> 1
5

such , We can observe from back to front , Maintain a head[i] Array , Indicates that the arc head in the input edge is i The number of the last side of , namely ：

head[1] = 6
head[2] = 2
head[3] = 3
head[4] = 7
head[5] = 0( That is, there is no arc head 5 The edge of )

We can also maintain it while saving to[i] Array , That is to say i The arc tail of the edge . This is too easy , Don't say .

Finally, we maintain next[i] Array , We set the first i The arc head of the edge is x, be next[i] Said in the first i The last arc before the edge is x Number of the side of , namely ：

next[1] = 0
next[2] = 0
next[3] = 0
next[4] = 1
next[5] = 0
next[6] = 4
next[7] = 5

After getting these three arrays , We can realize the edge adding operation .

void AddEdge (int u, int v, int x) {
    
	to[++ cnt] = v;
	w[cnt] = x;
	next[cnt] = head[u];
	head[u] = cnt;
}

When we want to enumerate the adjacency points of this point , Just use for Just loop through it .

for (int i = head[x]; i; i = next[i]) {
    
	//...
}

Example ： Adjacency table stores weighted undirected graph

Code

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1000 + 5;
int n, m, u, p, x, cnt, to[MAXN], head[MAXN], w[MAXN], next[MAXN];

struct node {
    
	int x, w;
	bool operator < (const node x) const {
    
		if (w == x.w) {
    
			return this->x < x.x;
		} else {
    
			return w < x.w;
		}
	}
};

vector <node> v;

void AddEdge (int u, int v, int x) {
    
	to[++ cnt] = v;
	w[cnt] = x;
	next[cnt] = head[u];
	head[u] = cnt;
}

int main () {
    
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i ++) {
    
		scanf ("%d %d %d", &u, &p, &x);
		AddEdge (u, p, x);
		AddEdge (p, u, x);
	}
	for (int i = 1; i <= n; i ++) {
    
		v.clear();
		for (int j = head[i]; j; j = next[j]) {
    
			v.push_back((node) {
    to[j], w[j]});
		}
		sort (v.begin(), v.end());
		for (int i = 0; i < v.size(); i ++) {
    
			printf ("%d ", v[i].x);
		}
		printf ("\n");
	}
	return 0;
}