Determine endpoint of a graph given as a list of nodes + direct successors and predecessors
It appears this is an instance of "incremental graph connectivity".  There are very efficient algorithms for this.

First, let's identify the weakly connected graph components and keep track of them as the graph changes.  In undirected graphs, it's easy to keep track of connected components as you add vertices and/or edges, using a union-find data structure.  In particular, each time you add a vertex, you use the MakeSet function to put it in a component of its own, and each time you add an edge, you use the Union function to merge the two associated components.  You can use this to keep track of the weakly connected components in your directed graph.

This can be done $O(\alpha(n))$ time per operation (i.e., per vertex or edge added).

Your "ends" are normally called "sink vertices".  You can keep track of the "ends" of each weakly connected component by associating a doubly linked list with each component; that list contains all of the sink vertices in that component.  Also, each sink vertex should have a pointer to the placed in the doubly-linked list where it appears.  When you merge two components, you can concatenate their lists in $O(1)$ time.  Also, when you add an edge, you check if this turns a sink vertex into a non-sink; if so, you follow the pointer from that vertex to find its place in the doubly-linked list, and remove it from the doubly linked list.  This too can be done in $O(1)$ time.  In all, this takes an additional $O(1)$ time per vertex or edge added, which is dominated by the cost of the union-find data structure.