当前位置:网站首页>Self study understanding of [chain forward star]
Self study understanding of [chain forward star]
2022-07-29 06:28:00 【C2024XSC249】
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;
}
边栏推荐
- Leetcode 189. rotation array
- 计算机网络面试题
- [beauty of software engineering - column notes] 16 | how to write project documents?
- Official tutorial redshift 04 rendering parameters
- SQL Developer图形化窗口创建数据库(表空间和用户)
- 官方教程 Redshift 09 Camera
- Summary of winter vacation training (1.23~1.28) [first tier]
- Eight sorts --------- quick sort
- Ue5 light shadow basic shadow full resolution sawtooth shadow solution lumen
- LeetCode #344.反转字符串
猜你喜欢
Unity中简单的cubecap+fresnel shader的实现
Leetcode 283. move zero
Traditional model predictive control trajectory tracking - circular trajectory (function package has been updated)
leetcode---技巧
2022暑初二信息竞赛学习成果分享1
Official tutorial redshift 07 instances and proxy
Shell tool finalshell
官方教程 Redshift 08 Light
Navicat for Oracle Cannot create oci environment
[beauty of software engineering - column notes] 16 | how to write project documents?
随机推荐
子网数、主机数与子网掩码的关系
Official tutorial redshift 03 parameters and general instructions of various GI
Learning notes of bit operation
[beauty of software engineering - column notes] 19 | as a programmer, you should have product awareness
关于时间复杂度的个人看法
Leetcode 19. delete the penultimate node of the linked list
Leetcode 3. longest substring without repeated characters
【Leetcode刷题】数组2——二分查找
虹科分享 | FPGA 实现的直通与存储转发切换延迟
Leetcode 557. reverse word III in string
Official tutorial redshift 05 system parameter detailed explanation
EtherCAT主站掉线后,如何保证目标系统免受故障影响?
Leetcode 83. delete duplicate elements in the sorting linked list
Official tutorial redshift 09 camera
Sqlyog installation and configuration tutorial
JUC concurrent knowledge points
虹科Automation softPLC | 虹科KPA MoDK运行环境与搭建步骤(2)——MoDK运行环境搭建
9196 tumor area solution
Shell tool finalshell
MySql-面试题