#P17914. Trajan Algorithm
Trajan Algorithm
题目描述
给定一张连通无向简单图,顶点编号为 至 。删除某个顶点及其关联的边后,如果剩余图的连通分量数增加,这个顶点就是割点。
考虑下面两个 DFS 程序。它们只有处理已经访问过的邻点时,更新 low 的方式不同。下面用参数 wrong 同时描述两个版本:wrong = false 是正确的 Tarjan 算法;wrong = true 是本题称作 Trajan 的错误算法。
search(u, d, wrong):
seen[u] = true
depth[u] = low[u] = d
children = 0
separated = false
按 adj[u] 中的顺序依次访问每个邻点 v:
如果 v == parent[u]: 跳过 v
如果 seen[v] == false:
parent[v] = u
search(v, d + 1, wrong)
children += 1
如果 low[v] >= depth[u]: separated = true
low[u] = min(low[u], low[v])
否则:
如果 wrong:
low[u] = min(low[u], low[v])
否则:
low[u] = min(low[u], depth[v])
如果 parent[u] 非空且 separated 为 true:
将 u 标记为割点
如果 parent[u] 为空且 children > 1:
将 u 标记为割点
每次运行前,所有 seen 都为 false,所有 parent 都为空,所有顶点都未被标记为割点。选择根 后执行 search(r, 0, wrong)。
对于每个顶点 ,判断是否存在某个根 ,以及一组表示给定图的邻接表顺序,使两个版本在 是否为割点的问题上给出不同结果。比较两个版本时,它们使用相同的根、相同的邻接表顺序,并分别重新初始化状态。
请输出所有满足条件的顶点。
输入格式
第一行是测试组数 。每组数据的第一行是 ,随后 行,每行两个整数 表示无向边。
输出格式
每组输出一行,按编号递增顺序输出所有满足条件的顶点,编号之间用空格分隔。如果没有,输出 Empty。
数据范围
,,。所有测试组的 之和、 之和分别不超过 。
边端点在 内。图连通,不含自环和重边。
样例
2
9 12
1 3
2 3
1 2
3 6
6 9
9 3
4 6
5 6
4 5
7 9
8 9
7 8
2 1
1 2
3 6 9
Empty