Шпоры по МПиПА / Графы / Определение числа компонент связности / Pascal / Исходник / ConnectionComponents

Program graph;

const max = 1000;
type myVector = array[0..max-1] of integer;
type myMatrix = array[0..max-1, 0..max-1] of integer;

var matrixOfSmejnost : myMatrix;
i, j : integer;
dimension : integer;

function numberConnectionComponents( dimension : integer; matrix : myMatrix ) : integer;
var temp1, temp2, sum : myMatrix;
i, j, k, step : integer;
components : myVector;
allComponentsFind : boolean;
maxComponent : integer;
begin
for i := 0 to dimension - 1 do begin
for j := 0 to dimension - 1 do begin
temp2[i,j] := 0;
end;
end;
for i := 0 to dimension - 1 do begin
temp2[i,i] := 1;
end;

sum := temp2;

for step := 1 to dimension do begin
temp1 := temp2;
for i := 0 to dimension - 1 do begin
for j := 0 to dimension - 1 do begin
temp2[i,j] := 0;
for k := 0 to dimension - 1 do begin
temp2[i,j] := temp2[i,j] + temp1[i,k]*matrix[k,j];
end;
end;
end;
for i := 0 to dimension - 1 do begin
for j := 0 to dimension - 1 do begin
sum[i,j] := sum[i,j] + temp2[i,j];
end;
end;
end;

maxComponent := 0;
for i := 0 to dimension - 1 do begin
components[i] := 0;
end;
allComponentsFind := true;
for i := 0 to dimension - 1 do begin
if ( components[i] = 0 ) then begin
allComponentsFind := false;
break;
end;
end;

while not allComponentsFind do begin
for i := 0 to dimension - 1 do begin
if ( components[i] = 0 ) then begin
j := i;
maxComponent := maxComponent + 1;
components[i] := maxComponent;
break;
end;
end;
for i := j + 1 to dimension - 1 do begin
if ( ( sum[j,i] > 0 ) or ( sum[i,j] > 0 ) ) and ( components[i] = 0 ) then begin
components[i] := maxComponent;
end;
end;
allComponentsFind := true;
for i := 0 to dimension - 1 do begin
if ( components[i] = 0 ) then begin
allComponentsFind := false;
break;
end;
end;
end;

numberConnectionComponents := maxComponent;
end;

begin
writeln('Connection components.');
write('Enter graph dimension: '); readln( dimension );
for i := 0 to dimension-1 do begin
write('Enter '); write( i + 1 ); write(' row: ');
for j := 0 to dimension-1 do begin
read(matrixOfSmejnost[i,j]);
end;
end;
readln;
write('Number connection components: '); writeln( numberConnectionComponents( dimension, matrixOfSmejnost ) );
writeln('Press Enter to continue...');
readln;
end.