How to solve is it a Tree on spoj using adjacency matrix?

general
, , ,
1

There is a comment on Problem. Which makes me feel it can be solved usiing adjacency matrix! But how… My solution times out!!

2

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).

3

Can it be solved using BFS??

4

Just beacuse we need to check whether a graph contains cycle or not and it think we can do it??

5

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.

1 Like