[Help] Graph Problem Help

Revision en1, by samalasathvikreddy7002, 2026-07-16 16:02:26

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:

  1. $$$u$$$ and $$$v$$$ are connected via a path of friendships.
  2. $$$u \neq v$$$
  3. $$$u$$$ and $$$v$$$ are not direct friends.
  4. $$$u$$$ and $$$v$$$ do not block each other.

I wrongly interpreted the problem and thinking of some other problem,

The Modified Problem: For any vertex $$$u$$$, find the number of vertices $$$v$$$ such that:

  1. There exists a path from $$$u$$$ to $$$v$$$ that does not contain any vertex $$$w \in \text{Blockship}[u]$$$.
  2. $$$u \neq v$$$
  3. $$$u$$$ and $$$v$$$ are not direct friends.
  4. $$$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

Tags #help, #graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English samalasathvikreddy7002 2026-07-16 16:03:53 6 Small update
en1 English samalasathvikreddy7002 2026-07-16 16:02:26 917 Initial revision (published)