<p>What you want is a data structure for a problem called 'incremental reachability'.
There are multiple ways to construct such a data structure, all have some different update/query time tradeoffs. A very simple way to achieve the goal is to use an adjacency list and use BFS every time a user queries if node &quot;x&quot; is reachable from 1.
This gets you update time: O(1) and query time: O(m).</p>
<p>A more complicated idea is 'even-shiloach' trees [1], here a BFS tree is maintained efficiently.
Total update time: O(nm) Query time: O(1).</p>
<p>An experimental analysis of similar algorithms can be found in [2].</p>
<p>[1] Shimon Even, Yossi Shiloach: An On-Line Edge-Deletion Problem. J. ACM 28(1): 1-4 (1981) <a href="https://dl.acm.org/doi/10.1145/322234.322235" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/322234.322235</a></p>
<p>[2] Fully Dynamic Single-Source Reachability in Practice: An Experimental Study, Kathrin Hanauer, Monika Henzinger and Christian Schulz <a href="https://arxiv.org/abs/1905.01216" rel="nofollow noreferrer">https://arxiv.org/abs/1905.01216</a></p>
Disjoint Set Union with directed graph
<p>I understand the DSU strictly works with undirected graphs from this stack overflow question - <a href="https://stackoverflow.com/questions/61167751/can-we-detect-cycles-in-directed-graph-using-union-find-data-structure">Can we detect cycles in directed graph using Union-Find data structure?</a></p>
<p>Nevertheless, I am currently working on a problem that involves 400000 queries and a graph with at most 400000 nodes, in which there are two possible queries:</p>
<ul>
<li><p>Connect nodes a and b (directed, of course)</p>
</li>
<li><p>Output &quot;true&quot; if node &quot;x&quot; is reachable from node 1. Otherwise, print &quot;false.&quot;</p>
</li>
</ul>
<p>However, my original instinct was to use DSU; that obviously would not work. Any suggestions? Thank you.</p>