Given a simple undirected and connected graph with $$$N$$$ nodes and $$$M$$$ edges. Also two different nodes are given $$$a$$$ and $$$b$$$. We have to answer $$$q$$$ queries. Each query contains an integer $$$v$$$(i.e. a node) from $$$1$$$ to $$$N$$$, we need to answer if we remove node $$$v$$$ and all of it's adjacent edges from the given graph, do nodes $$$a$$$ and $$$b$$$ lies in the same connected component or not? All queries are independent.
Constraints
My partial solution
PS: This problem is not from any contest.
Any hints to solve the above problem are appreciated. Thanks.
calculate the biconnected components and articulation points. Then create a tree where each articulation point is a vertex and each biconnected component is a vertex and connect each biconnected component to all articulation points belonging to it. On this tree you can answere your queries based on path queries with HLD or Link-cut-trees (this also works if $$$a$$$ and $$$b$$$ are part of the query)
since $$$a$$$ and $$$b$$$ are fixed over all queries there is an even simpler solution: all $$$v$$$ for which the answer is no are the articulation points on a path from $$$a$$$ to $$$b$$$.
I got it. Thanks for the response.
Find a path from $$$a$$$ to $$$b$$$. Assume that the path is $$$a\rightarrow u_1\rightarrow u_2\rightarrow...\rightarrow u_k\rightarrow b$$$. So if v is a satisfying vertex then v must be one of these vertices $$$u_1, u_2,..,u_k$$$. Therefore, all we need to do is to figure out whether erasing $$$u_i$$$ and all of its adjacent edges could prevent reaching $$$b$$$ if you start from $$$a$$$.
For the sake of simplicity, denote $$$u_0 = a, u_{k+1} = b$$$. So for each $$$i$$$, you must find the largest index $$$t_i \ge i$$$ such that $$$u_{t_i}$$$ is reachable from $$$u_i$$$ without going through any node $$$u_0, u_1, u_2,..,u_{k+1}$$$ excepts $$$u_i$$$ and $$$u_{t_i}$$$. This could be done by running bfs/dfs for each node $$$u_0, u_1, u_2,..,u_k$$$.
So if $$$max(t_0, t_1, ..., t_{i-1}) \le i$$$ then $$$u_i$$$ is a satisfying node. For that reason, if while running bfs from node $$$u_i$$$ we reach node $$$v$$$, but $$$v$$$ has been visited by running bfs of previous node $$$u_j (j < i)$$$ then we do not have to revisit node $$$v$$$ anymore, since it only ensures that $$$t_i \le t_j$$$. Even though doing that could make $$$t_i$$$ not maximized as we need, but max($$$t_0, t_1, t_2,...,t_i$$$) is ensured to be maximized$.
The overall complexity is $$$O(N+M)$$$, because even we run bfs many times, each node is visited at most once.
Thanks. i got the idea. It is somewhat similiar to finding cut vertex in a graph.