Loading... 对于图或树，一般有邻接矩阵和邻接表两种储存方式。其中，邻接矩阵更加直观，a[i]\[j]表示第i个点到第j个点的权值，值为0则表示无边；邻接表更适合以更小的空间储存稀疏图。 ~~接下来演示如何用邻接表收服一张图当宠物~~ ## 邻接表 > 图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。 > > 邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。 > > 在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。 > > 在无向图中，描述每个点所有的边(点a-点b这种情况) > > 与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。 邻接表可以看作“带有索引数组的多个数据链表”构成的结构集合 如下图，head和next数组保存的是ver数组的下标，相当于指针，其值为零表示指向空。ver数组储存了每条边的中点。另外edge数组储存每条边的权值（如果有的话）。 那么就有有向边(head[i],ver[head[i]])(head[i]!=0),(head[i],ver[next[head[i]]])(head[i]!=0 && next[head[i]]!=0)  这样，你就成功驯服了一张图。它有多种技能和附加功能，你可以用以下代码逗它玩 ```cpp //加入有向边(x, y),权值为z void add(int x, int y, int z){ ver[++tot] = y; edge[tot] = z; next[tot] = head[x]; head[x] = tot; } //访问从x出发的所有边 for(int i = head[x]; i; i = neat[i]){ int y = ver[i], z = edge[i]; //找到了一条有向边(x, y),权值为z } ``` 另外，可以用**vector**代替邻接表 ```cpp #include <vector> using std::vector; const int MAX_EDGE = 100000; vector<int> ver[MAX_EDGE], edge[MAX_EDGE]; //加入有向边(x, y),权值为z void add(int x, int y, int z){ ver[x].push_back(y); edge[x].push_back(z); } //访问从x出发的所有边 for(int i = 0; i < ver[x].size(); ++i){ int y = ver[x][i], z = edge[x][i]; //找到了一条有向边(x, y),权值为z } ``` ## 图与树的DFS  深度优先遍历：选择一个点作起点，访问这个点的所有边进行递归。 ```cpp void dfs(int x){ v[x] = 1; //记录点x被访问过 for(int i = head[x]; i; i = next[i]){ if(!v[ver[i]]) dfs(ver[i]); } } ``` 这段代码访问每个点和每条边恰好一次。 按照深度优先遍历的过程，依次给予每个节点第一次被访问1~N的标记，该标记就被称为**时间戳**，记为dfn 树上DFS时，对于每个节点，在刚进入递归后和即将回溯前个记录一次该点编号，最后产生的长度为2N的节点序列就称为树的**DFS序**  ```cpp void dfs(int x){ a[++m] = x; //a数组储存DFS序 v[x] = 1; for(int i = head[x]; i; i = next[i]){ if(!v[ver[i]]) dfs(ver[i]); } a[++m] = x; } ``` 每个节点x的编号在序列中恰好出现两次。设这两次出现的位置为L[X]和R[x]，那么闭区间[L[x],r[x]]就是以x为根的子树的DFS序。这可以将子树统计转化为序列上的区间统计。 ## 题解 家谱 ### 描述 ... 这一天小白拿到了自己家的家谱，小白便想知道自己家的家谱中，每位祖先有多少孩子（他孩子的孩子也是他的孩子）。但是家族历史源远流长，家谱实在太庞大了，自己一个人完全数不过来。热心的你便自告奋勇帮小白写一个程序，来统计每位祖先他有多少孩子。 ### 输入 输入的第一行有一个整数 n(1 ≤ n ≤ 100000)，表示家谱中总共的人数。 然后有 n-1行，每行有两个整数 x(1 ≤ x ≤ n), y(1 ≤ y ≤ n)表示 x 是 y 的父亲。 ### 输出 输出 n 行，每行有一个整数，表示第 i 个人他有多少孩子。 ### 题解 这是一个典型的求子树大小的问题。树的每一个分支的大小等于这个分支的分支的大小之和加1。所以使用记忆化搜索避免同一个分支重复搜索。 数据范围是100000，如果用邻接矩阵储存肯定内存会爆。这时候就要亮出我们的神兽——邻接表，避免族谱上小白的某个祖先有100000个孩子的空位。 ### 代码 ```cpp #include <iostream> #include <vector> using namespace std; int n, f[100010]; vector<int> ver[100010]; int dfs(int k){ if(f[k]) return f[k]; for(int i = 0; i < ver[k].size(); ++i){ f[k] += 1+dfs(ver[k][i]); } return f[k]; } int main(){ cin >> n; for(int i = 1; i < n; ++i){ int x, y; cin >> x >> y; ver[x].push_back(y); } for(int i = 1; i <= n; ++i){ cout << dfs(i) << endl; } return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 赞赏作者 微信
