12442 - Forwarding Emails

Difficulty : easy

Solution Description :

DFS problem

Read this line carefully in problem description - "they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves)"
i.e Each person send email only one. For each person has only one adjacency person. The input can not be (1 to 3, 2 to 3, 1 to 2) , because for person 1 here 2 adjacency person 3 and 2. 
So, you can represent this graph using one dimensional array adj[N].
Do not need to stack, you can use recursion.

Example:
4
1 2
2 1
4 3
3 2
The adjacency list, adj[1]=2, adj[2]=1, adj[3]=2, and adj[4]=3.
Use a boolean array visit[N]
visit[1]
visit[2]
visit[3]
visit[4]
False
False
False
False

At first start from 1
If visit[1]==false then run DFS in this time count the visited node and update the visit[] array 
(Set visit[i]=True here i is a visited node).  
Remember dot not use the array visit[] for cycle finding you can use another boolean array visit2[] for that purpose. 
After run DFS the visit[] array is
visit[1]
visit[2]
visit[3]
visit[4]
True
True
False
False
And count_visited_node=2 (1->2)

Now 2
visit[2]==true so, do not need to do anything.

Now 3
visit[3]==false so, run the DFS. After that the visit[] array is
visit[1]
visit[2]
visit[3]
visit[4]
True
True
True
False
And count_visited_node=3 (3->2->1)
Now 4
visit[4]==false so, run the DFS. After that the visit[] array is


visit[1]
visit[2]
visit[3]
visit[4]
True
True
True
True
And count_visited_node=4 (4->3->2->1)

For 4, the count_visited_node is maximum. Ans is 4.