首先，满足一个理论：
有k个无公共边的树形图 当且仅当 根到所有点 都有k条路径

一个简单的解法：

algorithm SPAN2; begin
find a spanning tree T1 rooted at r;
find a tree T2 rooted at r in G-- Tx with as many vertices
as possible;
while T2 is not a spanning tree do begin
a) find an edge v-->w in T1 such that v E T~, w r T2, and no descendants
x, y of w in T1 satisfy x-->y in T1, x E T2, and y r T,;
b) if w is not reachable from r in G--T2--{(v, za)} then add a new copy of
edge (v, w) to G;
comment after step b), w must be reachable from r]in G--T2--{(v, w)}
(where only one of the two possible copies of (v, w) is deleted) ;
replace T1 by a spanning tree rooted at r in G-- T2-- { (v, w)};
c) find a tree T, rooted at r in G-- T~ with as many vertices as possible;
end;
end SPAN2;

另外，我觉得出题者还是有点变态啊，这个解法自己想太难想了，不是每个人都是tarjan啊。
我觉得就出成只需要判断的就行。这样网络流就可以过了，至少一些人会吧。