La respuesta a algunas de esas preguntas requiere un algoritmo en sí misma. Por ejemplo, encontrar una arista (x,y) que está en G pero no en T podría implementarse recorriendo las aristas de G y verificando, para cada una, si está en T. Poder hacer esta verificación eficientemente requiere usar alguna estructura para representar T que lo habilite. Por ejemplo, si T se representa mediante un arreglo parent[] tal que para cada nodo u (representado como un índice de 1 a n) parent[u] nos da el padre de u en T, esa verificación se puede hacer en tiempo O(1) y la búsqueda de tal arista en tiempo O(m+n).
Para este problema en particular creo que es más sencillo resolver todo durante la recorrida DFS que hacerlo a posteriori a partir del árbol.
Saludos,
Álvaro
Para este problema en particular creo que es más sencillo resolver todo durante la recorrida DFS que hacerlo a posteriori a partir del árbol.
Saludos,
Álvaro