Strongly Connected Components

Python 2 using numpy, 71 62 bytes

import numpy
def g(M,n):R=(M+M**0)**n>0;print(R&R.T).argmax(0)

Takes input as a numpy matrix representing adjacency and the number of nodes. Produces output as a numpy row matrix that labels each vertex by the lowest vertex number in its component.

For an adjacency matrix M, the matrix power M**n counts the number of n-step paths from each start vertex to each end vertex. Adding the identity to M via M+M**0 modifies the adjacency matrix to add a self-loop to every edge. So, (M+M**0)**n counts paths of length at most n (with redundancy).

Since any path has length at most n, the number of nodes, any (i,j) where vertex j can be reached from i corresponds to a positive entry of (M+M**0)**n. The reachability matrix is thenR=(M+M**0)**n>0, where the >0 works entrywise.

Computing the entrywise and as R&R.T, where R.T is the transpose, then gives a matrix indicating the pairs of mutually reachable vertices. It's ith row is an indicator vector for vertices in the same strongly connected component as it. Taking its argmax of each row gives the index of the first True in it, which is the index of the smallest vertex in its component.

JavaScript (ES6), 125 bytes

a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))

Takes a list of directed pairs as an argument, while the result is a array for each vertex giving the first vertex strongly connected to it, which I believe counts as a valid labelling. For example, with the input [[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]] it returns [, 1, 1, 3, 3, 1, 6, 6, 3] (there is no vertex 0; vertexes 1, 2 and 5 have label 1; 3, 4 and 8 have label 3 while 6 and 7 have label 6).

MATL, 26 22 bytes

tnX^Xy+HMY^gt!*Xu!"@f!

This uses the same approach as @xnor's answer.

Works in current version (15.0.0) of the language.

Input is the adjacency matrix of the graph, with rows separated by semicolons. The first and last test cases are

[0 1 0 1; 0 0 1 0; 1 0 0 0; 0 0 0 0]

[0 1 0 0 0 0 0 0; 0 0 1 0 1 1 0 0; 0 0 0 1 0 0 1 0; 0 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0; 0 0 0 1 0 0 1 0]

Try it online!

t     % implicitly input adjacency matrix. Duplicate
n     % number of elements
X^    % square root
Xy    % identity matrix of that size
+     % add to adjacency matrix
HM    % push size again
Y^    % matrix power
g     % convert to logical values (0 and 1)
t!*   % multiply element-wise by transpose matrix
Xu    % unique rows. Each row is a connected component
!     % transpose
"     % for each column
  @   %   push that column
  f!  %   indices of nonzero elements, as a row
      % end for each. Implicitly display stack contents