|
|
|
|
|
|
by hermanschaaf
2299 days ago
|
|
|
Here is another one I thought of the other day. Q: Given V (the number of vertices), E (the number of edges) and L (a list of the edges) for a connected undirected graph, determine whether the graph is a tree. ---- A: It can be done in O(1) by:
return V == E + 1 The number of vertices in a tree is always one more than the number of edges. We also know that the graph is connected, so it has to be a tree. |
|
|