PAT1 1021 Deepest Root

题目链接 我的github

题目大意

给一个无向图

如果这个图是一个连通图，则求这个图的生成树中深度最大的树的根节点。如果这个图不是连通图，求其连通分量

输入

每组包含一个测试用例，每个用例的第一行是一个正整数$N$($\le 10^4$)，表示节点的数量，节点编号从$1$~$N$，接着有$N-1$行，每行有两个数表示图中边的两个端点

输出

如果是一个连通图，则输出图的生成树中深度最大的树的根节点（如果有多个从按照编号从小到大输出，每个编号为1行）如果这个图不是连通图，输出Error: K components，K是图的连通分量

样例输入

5 1 2 1 3 1 4 2 5

5 1 3 1 4 2 5 3 4

样例输出

3 4 5

Error: 2 components

解析

这题首先想到的是dfs来求连通分量。 至于要求图中深度最大的生成树，其实只用两次dfs就可以：

第一次dfs从图中任一点出发，在从这个点出发所能到达深度最大的节点必然是这个图中深度最大的生成树的一端（这里说一端是因为图是无向图，所以树的根节点也可以是叶子节点）我们要求的是深度最大的生成树的所有根节点，所以使用第二次dfs。从第一次dfs出来的一端开始，这样就能找到这个生成树的另一端，最后将第一次dfs和第二次dfs找到的点合并，再按序输出即可 n = 0 edge = list() # 邻接表存放图 vis = list() # 判断节点是否访问过 maxDepth = 0 # 最大深度 root = list() # 暂存的根节点 def dfs(node, d): global maxDepth, root, vis if d > maxDepth: # 判断当前深度是否大于最大深度 maxDepth = d root.clear() root.append(node) elif d == maxDepth: # 如果当前深度等于最大深度 root.append(node) vis[node] = True for i in edge[node]: if not vis[i]: dfs(i, d + 1) def solve(): global n, edge, root, vis n = eval(input()) edge = [[] for i in range(n + 1)] for i in range(n - 1): a, b = map(int, input().split()) edge[a].append(b) edge[b].append(a) vis = [False for i in range(n + 1)] k = 0 # 连通分量 s = 0 ans = [False for i in range(n + 1)] # 桶排序 for i in range(1, n + 1): if not vis[i]: k += 1 dfs(i, 1) if i == 1: if len(root): s = root[0] for j in root: ans[j] = True if k >= 2: print("Error: %d components" % k) else: vis = [False for i in range(n + 1)] dfs(s, 1) for i in root: ans[i] = True for i in range(1, len(ans)): if ans[i]: print(i) if __name__ == "__main__": solve()