终于搞懂为什么这道题,要对每一个节点标记一下是否访问过啦!!
为什么从任意节点dfs就可以?为何从任意一个点开始dfs,就可以模拟到删除每个点时的情况?
1.本题采用了邻接表存储有向图的方式,存储了无向无环图(树),任意点之间互连
2.采用st数组记录某点是否访问过,比如先dfs(1),那么访问到4号点的时候(dfs(4)时),因为1已经访问过,就只能访问其他未访问的邻点所在连通块(子树),并计算这些连通块的点数。虽然此时1所在连通块无法访问,但是可以通过n-sum的方式计算这个连通块的节点数。因此,利用n-sum,res和st数组,dfs到每一个节点,就能模拟到删除该节点的情况。
还是感谢大佬的评论