cuom1999's blog

By cuom1999, 5 weeks ago, In English

I'm thinking about this problem that seems very natural but I don't know if there is any online judge to submit:

Given a graph of 2-way friendship with $$$n$$$ vertices and $$$m$$$ undirected edges. For each person $$$u$$$, let's recommend him/her a person $$$v$$$ such that: $$$v$$$ is not a friend of $$$u$$$, and $$$v$$$ has the biggest number of common friends with $$$u$$$. In case of ties, any answer is accepted. If $$$u$$$ is already friend with everyone, print $$$-1$$$. Number of common friends between $$$u$$$ and $$$v$$$ is number of people that are friends of both $$$u$$$ and $$$v$$$.

A simple brute-force solution will solve this in $$$O(mn)$$$. A solution involving adjacency matrix will solve it in $$$O(m\sqrt{m})$$$ but requires $$$O(n^2)$$$ space by counting how many paths of length $$$2$$$ from $$$u$$$ to $$$v$$$ for all pairs $$$(u, v)$$$. Can we solve it better?

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can you explain your adjacency matrix solution?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Suprisingly , this was given by our teacher as a lab assignment xD

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

You can mark all the friends of 'u' and in turn keep a count of all friends of 'v' which are also friends of 'u' such that there is no edge between 'u' and 'v'. This can be done in O(m). Then you just need to find suitable 'v' which has this count as maximum. I don't know if I understood the question correctly, otherwise, this solution should work, right?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for EACH person. So time complexity of your solution is O(nm).