Count sources (Editorial)

To solve the problem, it is convenient to switch from the adjacency list representation to an adjacency matrix of the graph.

Construct an adjacency matrix of size n \times n, where a_{ij} = 1 if there is a directed edge from vertex $i$ to vertex $j$, and $0$ otherwise.

Next, for each vertex $j$, count the number of incoming edges. This can be done by summing the elements of the $j$-th column of the adjacency matrix.

A vertex is a source if and only if no edges enter it, that is, the sum of the elements in the corresponding column is $0$.

Thus, the answer is the number of vertices for which the number of incoming edges equals zero.

Example

The graph has one source — vertex $4$, since no edges enter it.

Algorithm implementation

Declare an adjacency matrix and an array $in$, where $in[i]$ stores the number of edges entering vertex $i$.

#define MAX 101
int g[MAX][MAX], in[MAX];

Read the input data. Based on the given adjacency list, construct the adjacency matrix.

scanf("%d", &n);
for (i = 1; i <= n; i++)
{

For each vertex $i$, first read the number of outgoing edges $k$.

  scanf("%d", &k);
  for (j = 0; j < k; j++)
  {

For each edge $(i,x)$, set g[i][x] = 1.

    scanf("%d", &x);
    g[i][x] = 1;
  }
}

Iterate over all pairs of vertices, traversing the adjacency matrix. For each edge $(i,j)$, increment $in[j]$ by $1$, since the edge $(i,j)$ enters vertex $j$.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  if (g[i][j] == 1) in[j]++;

Count the number of source vertices — that is, vertices with no incoming edges (for which in[i] = 0).

int source = 0;
for (i = 1; i <= n; i++)
  if (in[i] == 0) source++;

Print the answer.

printf("%d\n", source);