#P17914. Trajan Algorithm

Trajan Algorithm

题目描述

给定一张连通无向简单图,顶点编号为 11 至 nn。删除某个顶点及其关联的边后,如果剩余图的连通分量数增加,这个顶点就是割点。

考虑下面两个 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 都为空,所有顶点都未被标记为割点。选择根 rr 后执行 search(r, 0, wrong)。

对于每个顶点 uu,判断是否存在某个根 rr,以及一组表示给定图的邻接表顺序,使两个版本在 uu 是否为割点的问题上给出不同结果。比较两个版本时,它们使用相同的根、相同的邻接表顺序,并分别重新初始化状态。

请输出所有满足条件的顶点。

输入格式

第一行是测试组数 TT。每组数据的第一行是 n,mn,m,随后 mm 行,每行两个整数 u,vu,v 表示无向边。

输出格式

每组输出一行,按编号递增顺序输出所有满足条件的顶点,编号之间用空格分隔。如果没有,输出 Empty。

数据范围

1≤T≤1041\le T\le10^4,2≤n≤1052\le n\le10^5,1≤m≤1051\le m\le10^5。所有测试组的 nn 之和、mm 之和分别不超过 10610^6。

边端点在 [1,n][1,n] 内。图连通,不含自环和重边。

样例

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