Reposts[CodeForces-522A]
- VK Cup 2015 - Qualification Round 1
时间限制 1000ms 内存限制 256MB
这道题主要是求最大遍历深度，不难想到用DFS解。这道题数据量不大，暴搜可以直接过，所以本身题目没啥难度，只是建图的时候要用map处理一下字符串和图的顶点的对应关系。但是自己的DFS写的真叫一个狗屎，索性好好分析一下DFS的整个过程，来作为这道题的题解。
在算法导论书中，给出了进行DFS所需要的必备的储存信息：
当前顶点需要一个前驱$v.π$，用来跟踪DFS结束时构成的深度优先树。，当前顶点被访问到的时间戳$v.d$和完全访问后染成黑色的时间戳$v.f$（实际上，$v.d$也可以理解为跟源节点到当前位置的距离有关，也就是和深度有关，而$v.f$是回溯时才记录，跟深度就不好相关了。），除此之外，还需要一个染色$v.color$，用来记录当前顶点的颜色。其实这个染色的属性是用来判断当前节点走没走过，在算导书中提及，染色节点只要包括两种颜色就行了，因此实际上只需要一个布尔值。
DFS的开始，是在给定的图$G(V,E)$中，选择每一个可能的顶点，也就是$∀u∈G.V$，依次进行DFS。二叉树的DFS遍历，其实就是图的DFS的特例，因为二叉树的起始顶点只有树根。在DFS过程中，设当前顶点为$u$，先将$u$染色为$black$（$u.color=black$），然后选择所有有边连接的顶点$∀u′∈G:Adj[u]$，判断是否被染色，对于没有染色，也就是没有走过的顶点，继续进行DFS，直到没有顶点可以走为止。没有顶点可以走，意味着所有的顶点都被染色了，或者直接这个顶点没有连接任何下一个顶点。实际上，在上述描述的DFS过程中，无需额外设置递归的出口，因为选择合法的$u′$已经暗含了递归出口。需要注意，当DFS子过程回溯到主体过程时，需要重置所有顶点的染色标记和前驱标记。
下面考虑具体实现的问题：一是图选择何种表示方法。通常情况下，稀疏图采用邻接表的方法，这样能够避免大量的空间浪费。因为采用邻接矩阵的方法，有$V$个顶点的图，就需要$V×V$的矩阵，也就是$V^2$的空间；并且搜索时，必须依次扫描当前顶点是不是存在着到别的顶点的边，因此总的时间复杂度是$O(V^2)$，在假定稀疏图$E<<V$的情况，邻接矩阵相较于邻接表的$O(V+E)$还是较慢的。对于邻接表中的表，通常的定义为链表，但是能够自由扩张的顺序数据结构都是可以的。因此我在做题的时候，采用了STL中的vector容器，来作为图的邻接表表示。至于染色属性的选择，既可以将图的每一个顶点定义成结构体，也可以单独设置数组，作为染色标记。我在这里采用了后一种的处理方法。
对于数组作为邻接表的表示方法，我一开始把下标搞混了，一直得不到正确的结果。以我写的DFS过程为例，id参数表示当前顶点，用一个循环遍历vector容器表示的邻接表寻找有边连接的下一个顶点，因此判断下一个顶点是否被染色时，gone数组的下标实际上是下一个顶点graph[id][i]，而不是id和i的任意一个，i在这里表示用vector容器实现的邻接表在当前为id的顶点所包含的相邻的第i个顶点。除此之外，试图将判重和记录深度用一个属性来表示，似乎并不可行。
下面给出我AC的完整代码，供参考。
1 #include2 #include 3 #include 4 #include 5 #include
，