我们首先来看一下什么是前向星.
前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,
并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.
用len[i]来记录所有以i为起点的边在数组中的存储长度.
用head[i]记录以i为边集在数组中的第一个存储位置.
建图
int e[N], ne[N], h[N], idx;
int c[N];
void add(int a, int b)//建立一条a-->b的边
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}dfs
void dfs(int a)
{
c[a] = 1;
for (int j = h[a]; j != -1; j = ne[j])
{
int i = e[j];
if (!c[i])
dfs(i);
}
}bfs
void bfs(int x)
{
queue<int>q;
q.push(x);
c[x] = 1;
while (!q.empty())
{
int i = q.front();
q.pop();
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
if (c[k] == 0)
{
c[k] = 1;
q.push(k);
}
}
}
}