Here is the problem statement
http://www.spoj.com/problems/PT07Y/
For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the numebr of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. ( Every time we are on some node, we calculate the number of his neighbours which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any otehr trees apart form our graph.
http://www.spoj.com/problems/PT07Y/
For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the numebr of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. ( Every time we are on some node, we calculate the number of his neighbours which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any otehr trees apart form our graph.
No comments:
Post a Comment