There is a comment on Problem. Which makes me feel it can be solved usiing adjacency matrix! But how… My solution times out!!
Here is solution with adjacency matrix - http://pastebin.com/2VzfLZSs.
However, using adjacency list will make it run in O(N+M) instead of O(N^2).
Can it be solved using BFS??
Just beacuse we need to check whether a graph contains cycle or not and it think we can do it??
You only need to check that given graph is connected. It can be done in any way you prefer - with DFS, BFS, DSU and so on.