Так как граф ненаправленный, то матрица смежности симметрична. То есть можно гадить в одну половину и использовать вторую для восстановления исходной матрицы смежности.
#include <stdio.h>
#define NUM_VERTICES 6
void find_reachable(char adj[NUM_VERTICES][NUM_VERTICES],
unsigned int v,
unsigned int reachable[NUM_VERTICES])
{
unsigned int k, i, j;
for(k = 0; k < NUM_VERTICES; k++)
for(i = 0; i < NUM_VERTICES; i++)
for(j = i + 1; j < NUM_VERTICES; j++)
{
char v1 = (k > i) ? adj[i][k] : adj[k][i];
char v2 = (k < j) ? adj[k][j] : adj[j][k];
adj[i][j] = adj[i][j] || (v1 && v2);
}
for(i = 0; i < NUM_VERTICES; i++)
reachable[i] = v < i ? adj[v][i] : adj[i][v];
reachable[v] = 1;
for(i = 0; i < NUM_VERTICES; i++)
for(j = i; j < NUM_VERTICES; j++)
adj[i][j] = adj[j][i];
}
void printMatrix(char m[NUM_VERTICES][NUM_VERTICES])
{
int i, j;
for(i = 0; i < NUM_VERTICES; i++)
{
for(j = 0; j < NUM_VERTICES; j++)
printf("%d ", m[i][j]);
printf("\n");
}
}
int main(int argc, const char * argv[])
{
int i, v;
char rm[NUM_VERTICES][NUM_VERTICES] = { { 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0 }};
unsigned int result[NUM_VERTICES];
printf("Adjacency matrix:\n");
printMatrix(rm);
printf("\n");
for(v = 0; v < NUM_VERTICES; v++)
{
find_reachable(rm, v, result);
printf("Reachability vector for vertex %d: ", v);
for(i = 0; i < NUM_VERTICES; i++)
printf("%d ", result[i]);
printf("\n");
}
printf("\n");
printf("Adjacency matrix again:\n");
printMatrix(rm);
printf("It's not corrupted ;\n");
return 0;
}