[NFLS 1454/4] 一九八四 题解

大意

给定一个无向图, 有若干询问，分两种.

1. 不经过某条边 $x \to y$，$a$ 是否能到达 $b$ ;
2. 不经过某个点 $x$，$a$ 是否能到达 $b$ ;

题解

先跑一遍 $Tarjan$ , 建出 $dfs$ 树.

设 $dep_x > dep_y$ .

询问一:

1. $x \to y$ 为非树边，可以到达;
2. $a, b$ 都在或都不在 $x$ 的子树中，可以到达;
3. $x \to y$ 并不是割边，可以到达;
4. 否则，无法到达;

询问二:

1. 若 $a$ 在 $x$ 的子树中，将 $a$ 向上跳至 $x$ 的直接儿子，此时 $x$ 必须不是割点;
2. $y$ 同理;
3. 假如跳完后 $a$ 和 $b$ 为同一点，可以到达;