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 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<vector> 5 #include<map> 6 #include<algorithm> 7 using namespace std; 8 map<string, int> mapper; 9 vector<int> graph[205]; 10 int gone[205]; 11 int n; 12 int cnt = 0; 13 int ans = -2; 14 int proc(string & s) 15 { 16 for (int i = 0; i < s.size(); i++) 17 if (s[i] >= 'A'&&s[i] <= 'Z')s[i] += 32; 18 map<string, int>::iterator it = mapper.find(s); 19 if (it == mapper.end()) 20 { 21 mapper.insert(pair<string, int>(s, cnt)); 22 return cnt++; 23 } 24 return it->second; 25 } 26 void dfs(int id, int time) 27 { 28 gone[id] = 0; 29 for (int i = 0; i < graph[id].size(); i++) 30 { 31 if(gone[graph[id][i]]!=-1||graph[graph[id][i]].empty()) 32 { 33 ans = max(ans, time + 1); 34 return; 35 } 36 dfs(graph[id][i], ++time); 37 } 38 } 39 int main() 40 { 41 cin >> n; 42 string tmp1, tmp2; 43 while (n--) 44 { 45 cin >> tmp1; 46 cin >> tmp2; 47 cin >> tmp2; 48 int id1 = proc(tmp1); 49 int id2 = proc(tmp2); 50 graph[id1].push_back(id2); 51 } 52 for (int i = 0; i < cnt; i++) 53 { 54 for (int j = 0; j < 205; j++)gone[j] = -1; 55 dfs(i, 0); 56 } 57 cout << ans + 1; 58 return 0; 59 }
，