GRAPH

#include "stdafx.h" #include <stdio.h> #include <math.h> #include <conio.h> int i, j, k, c, n, min, ras, p; int A[10][10]; int C[10][10]; int B[10][10]; void A_0(int n) // обнуление и печать матрицы А { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (i == j) { A[i][j] = 0; } else { A[i][j] = 32000; }; }; }; } void A_adj(int n) // матрица смежности исходного графа записанная в А { while ((i != 0) || (j != 0)) { scanf("%i%i", &i, &j); A[i][j] = 1; }; } void AB1(int n) // умножение матрицы А на В один раз и запись результата в С { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { min = 32000; for (k = 1; k <= n; k++) if (A[i][k] + B[k][j] <= min) { C[i][j] = A[i][k] + B[k][j]; min = C[i][j]; }; }; }; } void C_fin(int n) { for (i = 1; i <= n; i++) // обнулить матрицу С и напечатать { for (j = 1; j <= n; j++) { C[i][j] = 0; }; }; for (i = 1; i <= n; i++) // заполнить матрицу В значениями матрицы А и напечатать { for (j = 1; j <= n; j++) { B[i][j] = A[i][j]; }; }; AB1(n); } void main() { printf("n: "); scanf("%i", &n); A_0(n); A_adj(n); C_fin(n); printf("\n"); ras = n - 1; //количество перемножений матриц А на В (н-1 степень) for (p = 2; p <= ras; p++) { AB1(n); for (i = 1; i <= n; i++) // заполнить матрицу A значениями матрицы C и напечатать { for (j = 1; j <= n; j++) A[i][j] = C[i][j]; }; }; int zero_count; printf("istoki: \n"); for (i = 1; i <= n; i++) //опредение истоков { zero_count = 0; for (j = 1; j <= n; j++) if ((C[i][j] == 0)|| (C[i][j] == 32000)) zero_count++; if (zero_count == 1) printf("%i ", i); } printf("\n"); zero_count = 0; printf("stoki: \n"); for (j = 1; j <= n; j++) //опредение стоков { zero_count = 0; for (i = 1; i <= n; i++) if ((C[i][j] == 0) || (C[i][j] == 32000)) zero_count++; if (zero_count == 1) printf("%i ", j); } getch(); }