众所周知,OI 中图的存储主要有两种方式:使用 std::vector
实现的邻接表,以及链式前向星。前者的常数较大,有时候会出现卡不过去的情况,但是支持 range-based for 循环,遍历的时候代码更简洁。可不可以在使用链式前向星的同时,使用 range-based for 循环呢?如以下代码所示:
Graph graph;
int u;
...
for (v : graph[u]) {
...
}
为了支持 range-based for 循环,graph[u]
需要支持 begin()
、end()
。这两个函数的返回值为迭代器,需要重载 !=
和前缀 ++
运算符。我们可以定义一个迭代器类型,内部有指向原图的指针,以及一个整数,表示边的编号。为了方便,graph[u]
的类型也是它,graph[u].begin
的返回值等于 graph[u]
。
struct Graph {
int cnt, head[V], nxt[E], to[E];
struct Iter {
Iter(Graph *g, int i) : g(g), i(i) {}
Graph *g;
int i;
bool operator!=(Iter &o) { return i != o.i; }
Iter operator++() {
i = g->nxt[i];
return *this;
}
int operator*() { return g->to[i]; }
Iter begin() { return *this; }
Iter end() { return {g, 0}; }
};
Iter operator[](int i) { return {this, head[i]}; }
void link(int u, int v) {
nxt[++cnt] = head[u];
to[cnt] = v;
head[u] = cnt;
}
};
标签:return,int,graph,Iter,range,based,前向星
From: https://www.cnblogs.com/dingxutong/p/17690783.html