I believe you need this: start with random node and start to recursively traverse all connected nodes. After you went into neighbour node, delete link you came from from all link list (to avoid returns). Check if node in visited list (or map<node, bool>). If it is, then there is a loop and graph is not a tree. If it isn't add it to visited list (set map[node] to true). Continue traversal. If you went over all connections, and there is no loops check if all nodes were visited. If is, then it is a tree, otherwise there is freestanding nodes and it isn't a tree.
Well,I don't but since all I need is to check if the graph is a tree I choose one of the two nodes as a parent and the other as a child and that wouldn't change the fact whether it is a tree or not it just changes the tree shape.
I think that the problem is when there is a loop and separated nodes in the graph. It can't detect them I tried input like :
which is a graph with a loop and separated node and it output "YES"
but if I entered it that way it output "NO":
so generally, I need to check for cuts in the graph .
Thanks for both replies . I now know what is the problem .