Graph Theory: find the connected components of graph given the matrix 
I drew the graph but it's a complete mess so I assume there is some formula for this. 
I confess I am not entirely sure of what I am supposed to do here. I think I am supposed to find subsets of vertices among which there is  a path to each of them. So maybe I have to find the vertex or vertices which connect the two components somehow? 
 A: Writing the matrix out as a list of adjacencies
\begin{array}
 & & & 1\to 3 & 1 \to 4 & 1 \to 5 \\
 & & 2\to 3\\
 & & & & & 3 \to 6\\
4 \to 1 & 4 \to 2 & 4 \to 3 & &  4 \to 5 & 4 \to 6\\
 5\to 1 & 5 \to 2 & & 5 \to 4 & & 5 \to 6 \\
 & & 6 \to 3
\end{array}
some of the first things that jump out at us are:


*

*$4$ and $5$ are connected to lots of vertices and to each other

*$3$ and $6$ are connected to each other and nothing else.


So $\{3,6\}$ will be one connected component, since when you're at one of those vertices you're stuck and can't reach any others; $\{4,5,\dots\}$ is the beginning of another.
Looking at $1$, we see that it has edges to both of the components we've found so far; so it could become part of either one or start a new one. It can't be part of the $\{3,6\}$ component, because those vertices don't have a way to reach $1$, but vertices $4$ and $5$ do both have edges back to $1$ (just one of those would be enough). So $1$ joins $4$ and $5$ in a component $\{1,4,5,\dots\}$.
Looking at $2$, we see that it only has edges to $3$, so it is either a new component or part of the $\{3,6\}$ component. But it can't be part of that component, because neither $3$ nor $6$ has a way to reach $2$. So $\{2\}$ is its own component.
Now we've looked at all the vertices and obtained three components: $C_1 = \{1,4,5\}$, $C_2 = \{2\}$, and $C_3 = \{3,6\}$.
A: If you really want a formula, let's call $A$ your adjacency matrix of size $n$ (here, $n=6$).
$A$ represents all the paths of length 1 between two nodes, 
$A^2$ represents all paths of length 2 between two nodes, etc. Any path between two nodes in a graph with n nodes is at most of size $n-1$, so you need to compute $S = \sum\limits_{i=1}^{n-1}A^{i}$. $s_{ij}$ will then denote the number of paths of length at most $n-1$ between $i$ and $j$. There is a path between nodes $i$ and $j$ if and only if $s_{ij}$ is nonzero:
$$\begin{bmatrix} 
1 && 1 && 1 && 1 && 1 && 1 \\
0 && 0 && 1 && 0 && 0 && 1 \\
0 && 0 && 1 && 0 && 0 && 1 \\
1 && 1 && 1 && 1 && 1 && 1 \\
1 && 1 && 1 && 1 && 1 && 1 \\
0 && 0 && 1 && 0 && 0 && 1 \\
\end{bmatrix}$$
