Say you have an adjacency matrix like the one in your question. You can determine connected components by doing a breadth-first (or depth-first) search in the matrix without having to remake copies or delete vertices.
You'll start each connected component search with the first vertex that you haven't placed in a component yet. The first one will be vertex $v_1$:
Initialize the connected component $C_1 = \{v_1\}$ and then move across $v_1$'s row in the adjacency matrix. We see that $v_1$ is adjacent to $v_5$, so $v_5$ gets added to the component $C_1 = \{v_1,v_5\}$, and we move on to $v_5$'s row. $v_5$ is connected to $v_1$ (seen already) and $v_9$, so add $v_9$ to $C_1$, and move on to $v_9$, which is adjacent to $v_5$ (seen already). Since we've reached the end of this tree, we're done with this component and get $C_1 = \{v_1,v_5,v_9\}$.
Now, take the next vertex that we haven't seen yet ($v_2$) and set $C_2 = \{v_2\}$. $v_2$ is adjacent to $v_3$ and $v_6$, so we get $C_2 = \{v_2,v_3,v_6\}$, and the next vertex to check is $v_3$, which is adjacent to $v_2$ and $v_6$, both seen. Then move to the next vertex $v_6$ and note that its adjacent to $v_2$ and $v_3$ (both seen), so we're done with this component too.
On to $C_3$, the same procedure gets us $C_3 = \{v_4,v_7,v_8\}$. All vertices $v_1$ through $v_9$ have been seen at this point so we're done, and the graph has $3$ components.
Suppose that the graph $G$ contains $n$ vertices. Then
the largest number of steps it could take to go from a vertex to any other vertex is $n$ steps. If you can calculate the powers of the adjacency matrix $A$, then you should produce
$S = A + A^2 + \cdots + A^n$.
If there are any zeroes in the matrix $S$, it is impossible for
some pair of vertices to connect in $n$ steps or less, so this pair will never connect, and the graph is not connected.
There are ways to compute larger powers of $A$ by keeping track of the power of $A$ with an exponent that is a power of 2. Examples: $$A^3 = A^2A \\ A^6=A^4A^2 \\ A^{27}=A^{16}A^8A^2A^1$$ I recommend looking into the binary representation of your original exponent to find the powers of the corresponding "powers of 2" adjacency matrices. Then add them all up and see if the resulting matrix contains any zeros! If not, it is fully connected.
Best Answer
If coloring two different vertices gives the same graph upon isomorphism, this means that the two vertices are in the same orbit of the automorphism group. So your subsets are the orbits of the automorphism group. You can compute the orbits by computing the group automorphism of your graph. This is not a trivial problem (There is no polynomial algorithm found for it, even though it is believed not to be NP-complete), but there are practical algorithms, for example nauty's library. This library directly gives you the orbits.