Finding the number of weakly connected components of a digraph without knowing components using linear algebra Let's say that I have a graph where each vertex can have an outdegree of at most 1 (self-loops allowed). Finding/creating an algorithm to find the weakly connected components and then counting them is not difficult. But it seems weird to have to do both. Is there a way to find the number of weakly connected components without finding them as well, in a way that is faster than having to do both?
At first I thought about looking at restrictions on the numbers of zero columns compared to the number of zero rows, but couldn't get anywhere with that.
 A: The class of directed graphs you are describing are known as directed-pseudoforests, they entirely classify the functional graphs of every function with a finite domain. Here is one for example:

As you can see each vertex in the digraph above has an out-degree of at most one. Now one can also prove these are unicyclic meaning each weakly connected component contains at most one directed cycle (therefore the number of strong components is equal to the number of cycles in your digraph), this can be shown by noting a digraph is strong iff it can be expressed as a union of directed cycles now suppose some connected component has two directed cycles, then there must be an undirected path between the two since by assumption they belong to the same connected component. However if this were the case then there would be a vertex with out-degree greater then one, a contradiction. In contrast those connected components that contain no directed cycle are directed-trees with the arcs protruding inward, they are known as in-trees or "anti-arborescences". Now since every finite in-tree has exactly one sink vertex, this means each connected component contains a single strong component iff it has no sink vertices. Therefore if your digraph is $D$ and we denote the number of strong components in $D$ by $S$ while we denote the number of weak components in $D$ by $W$ then:
$$W-S=|V(D)|-|E(D)|=\text{Total number of sink vertices in }D\\=\text{ Total number of zero columns in the adjacency matrix of }D$$
Thus if you know either the number of weak components or the number of strong components in your digraph then you can compute the other. In other words you are correct you don't need to compute the strong component using Tarjan's algorithm if you know the total number of weak components, also your original idea of counting zero columns was the right idea.
