Je n'ai pas bien compris à quoi servait l'union find... dans un graphe orienté (!).

Question bonus 1 : Comment on fait pour avoir un précalcul en o(N²) ?
J'ai un algo en O(N²log(N)+Q) si on désoriente le graphe.
Avec un graphe orienté je n'ai pas mieux que O(QN²log(N)) (en théorie O(QN²+N²log(N)) pour ceux qui aiment coder un certain tas) ou O(N\^3).