Challenge 1: Gossip

**Admin** Sat Jun 04, 2011 9:43 am

Word got around about your laptop confiscation for playing Pokemon in History class. Everywhere you walk, you can hear your friends giggling about your misfortune. To avoid further embarrassment, you've vowed to not talk to anyone who knows this piece of news. But you don't know who knows about this, but you do know who are friends with whom. Luckily, your friends are very predicable and you know that if they hear gossip, they will spread it to all their friends, even if their friends may already know it. To help you in this, you'll need to write a program that, given a people who are friends with each other, find out who still doesn't know about your confiscation. Your program must first ask for number of friends you have (may be 0). Then it must ask for the size of the list N. Then it read in N lines of friends. Each line will be in this format:

1 2

This means that person 1 and person 2 are friends and will tell each other gossip. Then print out the list of people who don't know the news. You can assume that if 1 and 2 are friends, then 2 and 1 are friends. Also, all friends will be given in integers (their parents aren't very creative with names). The gossip always starts with person 1 (i.e. the gossip originates from person 1 and person 1 will tell all his friends).

Example:
Input:
Number of friends: 5
Size of list: 3
1 2
2 5
2 4
Output:
3

In the example above, person 1 will start gossiping to person 2. Then person 2 gossips to person 5 and person 4. However, person 3 still don't know the gossip, so your program should print out 3.

Test Case 1:
Friends: 6
Size: 3
2 3
1 5
4 5
Output: 2,3,6

Test Case 2:
Friends: 5
Size: 4
1 2
1 3
1 4
1 5
Output:

Hints:
1. Think about how to store the friend information? Given a friend, you'll need to find out his friends are.
2. You'll need to keep track of who knows the information already.
3. I can think of at least two different approaches, so there are many ways of solving this problem.
4. If you've got a solution, try thinking in reverse, maybe you can find a better and faster solution.
5. Recursion may help. (If you don't know what recursion is, search it up, it's awesome)