In this paper we consider a structured linear system represented by means of a directed graph. We present a graph theoretic method to compute the generic number of invariant zeros of the corresponding Rosenbrock matrix. The method is based on a fundamental decomposition of the directed graph representing the structured system. The generic number of invariant zeros is important in generic versions of problems involving controllability and pole placement.