Question

LinkedOUT is a new social network. Every pair of LinkedOUT users is either acquainted or not acquainted with each other. Two users u₁ and u₂ are approachable if there exists a sequence of users starting with u₁ and ending with u₂ where each adjacent pair of users in the sequence are acquainted. New user Weff Jeiner has just signed up for LinkedOUT and is not acquainted with anyone. Given a list of all pairs of users that are acquainted on LinkedOUT, describe an efficient algorithm to determine the minimum number of users with whom Weff needs to become acquainted in order to be approachable by every user on LinkedOUT.

Answer 1

The whole LinkedOut social network can be thought of an Undirected Graph.

Each user is denoted by a unique node in the graph. If two users u1 and u2 are acquainted then there exist edge between their representative nodes. If they are not acquainted then there is no edge between the nodes.

So LinkedOut can be uniquely represented as undirected graph G (E, V)

eg:

To find the minimum number of people to be acquainted initially such that we know the entire network is the same as

Find the minimum number of nodes such that from these nodes we can reach each node of the graph

Solution:

1. If the graph is fully connected then there exist path between any two nodes and knowing one node may be enough to get to any node in the graph

eg:

So knowing U4 is enough

2. If the graph is not fully connected then we can find its component and choose any one node from each connected component. Knowing those nodes is sufficient to reach each node

eg:

In the above graph, we have 3 connected components so knowing U4, U7, U10 from the respective component is enough to reach each node in the graph.

So just find connected component set and choose any node from each connected component

ALGORITHM :

To find connected component do Depth-first search or Breadth-first search

Pseudocode: