C++

C++ – chained forward star

_Redstone_c_

Forward star is a special edge set array. We sort each edge in the edge set array according to the starting point from small to large. If the starting points are the same, we sort each edge according to the end point from small to large.

And record the starting position and storage length of all edges starting from a certain point in the array, then the forward star is constructed.

Use $len[i]$ to record the storage length of all edges starting from i in the array.

Use $head[i]$ to record the first storage location in the array with i as the edge set.

So for the following picture

The order in which we enter the edges is

1 2
2 3
3 4
1 3
4 1
1 5
4 5

Then after sorting, you will get

编号:     1      2      3      4      5      6      7
起点u:    1      1      1      2      3      4      4
终点v:    2      3      5      3      4      1      5

get

head[1] = 1    len[1] = 3
head[2] = 4    len[2] = 1
head[3] = 5    len[3] = 1
head[4] = 6    len[4] = 2

However, there will be a sorting operation using forward star. If quick sorting is used, the time will be at least $\Omicron(n \log n)$

If you use chained forward stars, you can avoid sorting.

We establish the edge structure as

struct Edge {
     int next;
     int to;
     int w;
};

Where $edge[i].to$ represents the end point of the $i$-th edge, $edge[i].next$ represents the storage location of the next edge with the same starting point as the i-th edge, $edge[i].w $ is the edge weight.

There is also an array $head$, which is used to represent the storage position of the first edge starting from $i$. In fact, you will find that the storage position of the first edge here is actually

The number entered at the end of all edges starting from $i$.

The $head$ array is generally initialized to $-1$

The add function for adding edges is like this

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

Initialize $cnt = 0$

Add duplicate edges

void add_edge(int u, int v, int w) {
    for(int i = head[u]; ~i; i = edge[i].nxt) {
        if(edge[i].v == v) {
            if(edge[i].w > w)
                edge[i].w = w;
            return;
        }
    }
    tot++;
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].nxt = head[u];
    head[u] = tot;
}

Now let’s simulate it according to the above picture and input.

edge[0].to = 2;     edge[0].next = -1;      head[1] = 0;
edge[1].to = 3;     edge[1].next = -1;      head[2] = 1;
edge[2].to = 4;     edge[2],next = -1;      head[3] = 2;
edge[3].to = 3;     edge[3].next = 0;       head[1] = 3;
edge[4].to = 1;     edge[4].next = -1;      head[4] = 4;
edge[5].to = 5;     edge[5].next = 3;       head[1] = 5;
edge[6].to = 5;     edge[6].next = 4;       head[4] = 6;

Obviously, $head[i]$ saves the highest number among all the edges starting from $i$, and regards this as the position of the first starting edge of vertex $i$.

In this way, the traversal is performed backwards, which means that the input order is reversed, but this does not affect the correctness of the results.

For example, in the above figure, there are $1$ edges starting from node $3$, and their numbers are $0,3,5, 1, 5$ respectively, and $head[XNUMX] = XNUMX$

This is what happens when traversing all the edges starting from node u

for(int i=head[u];~i;i=edge[i].next)

That is to say, first traverse the edge numbered $5$, which is $head[1]$, then $edge[5].next$, which is the edge numbered $3$, and then continue $edge[3].next$ , that is, the edge numbered $0$, which can be seen to be in reverse order.

Complete sample

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e6; //点数
const int MAXM = 1e7; //边数
struct E {              //存边结构体
    int u;
    int v;
    int w;
    int nxt;          //下一条边在edge中的下标
} edge[MAXM];
bool vis[MAXN];
int head[MAXN];       //以节点i开头的边在edge中的开头下标
int tot = 0;          //edge中的边数
void init() {         //初始化
    memset(head, -1, sizeof head);//-1表示改点无出度
    memset(vis, false, sizeof vis);
}
//加边函数
void add_edge(int u, int v, int w) {
    tot++;
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
//实例
void dfs(int root) {
    vis[root] = true;
    printf("%d\n", root);
    for(int i = head[root]; ~i; i = edge[i].nxt)
        if(!vis[edge[i].v])
            dfs(edge[i].v);
}
int main() {
    init();
    int m;
    scanf("%d", &m);
    while(m--) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v, 0);
    }
    dfs(1);
    return 0;
}

Post Reply