I was solving this problem Smash Me
Abridge Problem Statement: Given $$$N$$$ users, $$$M$$$ friendship pairs, and $$$K$$$ blockship pairs. For each user $$$u$$$, find the number of other users $$$v$$$ such that:
- $$$u$$$ and $$$v$$$ are connected via a path of friendships.
- $$$u \neq v$$$
- $$$u$$$ and $$$v$$$ are not direct friends.
- $$$u$$$ and $$$v$$$ do not block each other.
I wrongly interpreted the problem and thinking of some other problem,
The Modified Problem: For every vertex $$$u$$$, find the number of vertices $$$v$$$ such that:
- There exists a path from $$$u$$$ to $$$v$$$ that does not contain any vertex $$$w \in \text{Blockship}[u]$$$.
- $$$u \neq v$$$
- $$$u$$$ and $$$v$$$ are not direct friends.
- $$$u$$$ and $$$v$$$ do not block each other.
I later was able to solve the original problem but just curious how to solve the above problem.
Thanks :D








Auto comment: topic has been updated by samalasathvikreddy7002 (previous revision, new revision, compare).
EDIT: on reflection this does not actually work because the problem requires vertex removal not edge removal.
The hard part of this can be solved by reducing to Offline Dynamic Connectivity (see https://codeforces.com/blog/entry/104443) I don't know if there is an easier solution
Isn't it equivalent to removing edges of all the Blockship nodes of any vertex $$$u$$$ ?
Yes, but there can be O(n) such edges, which blows up the complexity; the $$$q$$$ in the reduction becomes potentially $$$O(n*m)$$$ at which point you might as well just brute-force DFS from every node (which I assume is not intended to fit within the time limit)
Thanks for sharing, I feel like DSU(Union-find) can be used to solve this ?
We are equivalently finding articulation points and no of vertices after remove articulation points which belong to same connected component for any vertex $$$u$$$