I\'m trying to organise a large reunion though facebook. Over the years we\'ve a
ID: 654875 • Letter: I
Question
I'm trying to organise a large reunion though facebook. Over the years we've all drifted apart, and so there isn't anyone who is still facebook friends with everyone.
You need to be facebook friends to invite someone to the facebook event and I have invited all the people that I can. I also know that each of the uninvited people has at least one friend amongst the invited people, and by checking for 'mutual friends' I can know who they are.
In order to get everyone invited to the reunion I'm going to ask some of the invited people to invite the uninvited people.
My question is, does anyone happen to know an algorithm to find the minimum number of invited people that are required to message all of the uninvited people? I don't need anything super detailed, just something to point me in the right direction.
Explanation / Answer
One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends.
Now, assuming that you're asking people to invite their friends, and have those people invite their friends, and so on, then your problem basically boils down to finding the connected components of the graph you just made. (Two vertices are in the same connected component iff there exists a path between them)
Actually finding them isn't that bad; it's basically a slightly modified DFS.