Editorial for SAC '21 Code Challenge P5 - Friends of Friends

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

Each update can be added to an adjacency list to maintain the connections between students.

Each query can be answered by starting a BFS (breadth-first search) from the starting student and counting the amount of friends visited.

Time Complexity: \mathcal{O}(NQ)

Subtask 2

A disjoint-set can be used to maintain the connected components and query the amount of students in each component.

Time Complexity: \mathcal{O}(Q \log N)

Comments


  • 9
    suguruchhaya  commented on June 8, 2021, 5:20 p.m. ← edit 2

    (If you are unaware that there was a previous comment that was removed, skip this paragraph. I guess you could read this if you are the admin who removed the previous comments or if you commented on this previously.) OK so my previous comment stream was removed for some reason. My guess is that it seemed like it was a troll going in the wrong direction. Even though I barely know anyone on this website, I find it good that people comment on others to help each other out. That is exactly what I am trying to do commenting on these editorials. Not to criticize editorialists but some editorials are hard to understand and in my opinion, aren't specific enough. I often spend a lot of time struggling to solve questions. So when I eventually do, I make that step a little easier by commenting. Commenting helps me remember certain techniques to solve problems, which is also a plus for me. Commenting doesn't take that much time so I do it. Regardless of whether people orz me or maybe troll me, I don't take it personally but I just look at it and smile and enjoy that kind of interaction. I wasn't getting pissed at anyone (admin, commenters etc). I was just trying to explain my thought process. I don't want to get into any kind of online drama. I just comment for personal satisfaction and maybe helping someone out.

    Anyways, to the problem.

    If you don't know about disjoint sets, watch https://www.youtube.com/watch?v=wU6udHRIkcc.

    To save time, you have to balance out the nodes so that you can reach the parent in less steps. You don't have to implement collapsing find but I can imagine that you could do so using tail recursion. Like the video, you could either using a negative sign to indicate a parent (1 array) or you can use 2 separate arrays for rank (how many nodes it carries) and parent (the parent of that node).


    • 8
      Riolku  commented on June 8, 2021, 5:33 p.m. ← edited

      You might notice that the editorialist left a link explaining this data structure. Leaving code in editorials is discouraged as it encourages people to copy the code without understanding the solution.