Блог пользователя samalasathvikreddy7002

Автор samalasathvikreddy7002, история, 7 недель назад, По-английски

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 every 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

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
7 недель назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by samalasathvikreddy7002 (previous revision, new revision, compare).

»
7 недель назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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.me/blog/entry/104443) I don't know if there is an easier solution