#include <iostream>
#include <queue>
#include <Windows.h>
using namespace std;

int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout << "Додаткове завдання №6" << endl << "Бершадський Андрій Денисович ІС-81" << endl << endl;//вивід даних про роботу
    int n;
    cout << "Введіть кількість вершин графу: ";
    cin >> n;
    bool arr[100][100];
    cout << "Заповнення матриці суміжності: " << endl;               //заповнення матриці суміжності з клавіатури
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j]) {                                // якщо інснує орієнтоване ребро, з'єднуюче вершини i и j
                for (int z = 0; z < n; z++) {
                    if (arr[j][z] && !arr[i][z]) {                      // якщо з вершини j в вершину z йде ребро, але із i в z - ні, то граф нетранзитивен
                        cout << "Ні, граф не є транзитивним" << endl;
                        system("pause");
                        return 0;
                    }
                }
            }
        }
    }
    cout << "Так, граф є транзитивним" << endl;
    system("pause");
    return 0;
}