Another one potentially for this list is tokei[1] I was trying to count the code in our repos at work and used the venerable 'cloc' utility. It took over 5 minutes. Looking around I found tokei, written in rust. Same-ish results (more accurate actually) took 10 seconds.
As far as complexity goes, this should be linear in number of vertices. In fact, you don't even really have to construct the graph, just count out degree.