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?
Can you explain your adjacency matrix solution?
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?
for EACH person. So time complexity of your solution is O(nm).