前向星就是用数组来模拟链表,添加边的操作就是链表的头插,而用vector的话就是模拟链表的尾插,总之怎么插都无所谓,我们只要把与某个点有关联的点存起来就行了。


struct nodes
{
    int next;
    int v;
    int w;
}edge[10001];

看到这个结构是不是有点眼熟,是不是跟链表的节点很相似。(没错,我们本来就是要用数组来模拟链表)
下面来解释一下这些变量:

  • next 表示下一条边的下标
  • v表示这条边的终点
  • w表示这条边的权值

接下来就是比较重要的东西了, head数组;
head数组:

  • 下标:下标是某条边的起点
  • 值: head[u]表示的是以u为起点的边的下标

说起来可能有点抽象,我们来演示一下:
假设存在这样一个邻接表(vector实现):
1: 2 3
2:4 5
3:5
4:5
5:null
(画出来应该不难)
0:1--2
1:1--3
2:2--4
3:2--5
4:4--5
5:5(没了)
head[1]保存的就是最后一条以1为起点的最后一条边的下标这里head[1] == 0;
head数组要全部初始化成一个标记,表示这他为空,一般为-1


操作

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

前两行是边的初始化,很简单。
下面两行就是链表的头插。
新边(新节点)的next指向以原表头
然后更新表头,注意这里head存的是下标

上面的栗子:
1--2
1--3

现存1--2;
edge[0].v = 2;
edge[0].next = head[1];//head[1] == -1;
head[1] = 0;//起点为1的点是第一条(0)

然后1--3
edge[1].v = 3;
edge[1].next = head[1];//head[1] == 0; 第二条边成功指向第一条边

head[1] = 1;//现在表头更新了

  • 遍历
    以u为起点
for(int i=head[u]; i!=-1; i = edge[i].next)
{
    //context
}

来一道题
SDUT 3117

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 500005;
struct nodes
{
    int next;
    int v;
    int w;
}edge[maxn];
int head[maxn];
int cnt;
void add(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m;
    while(cin >> n >> m)
    {
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(int i(0); i<m; i++)
        {
            int u, v;
            cin >> u >> v;
            add(u, v, 1);
        }
        int q;
        cin >> q;
        while(q--)
        {
            int u, v;
            int flg = 0;
            cin >> u >> v;
            for(int i=head[u]; i!=-1; i = edge[i].next)
            {
                if(edge[i].v == v)
                {
                    flg = 1;
                }
            }
            if(flg)
                cout << "Yes" << endl;
            else
                cout << "No"  << endl;
        }
    }
    return 0;
}


/***************************************************
Result: Accepted
Take time: 64ms
Take Memory: 948KB
Submit time: 2019-01-02 10:54:53
****************************************************/