Поиск циклов в графе. Поиск центра взвешенного графа

#include <iostream>
#include <vector>
using namespace std;
 
int N; // кол-во вершин в орграфе
std::vector< std::vector< bool > > g; // представление графа в виде матрицы смежности
std::vector< bool > pre; // здесь будем помечать пройденные вершины на прямом ходу
std::vector< bool > post; // здесь будем помечать пройденные вершины на обратном ходу, пометка вершин на обратном ходу нужна чтобы определять тип ребра в остовном дереве
 
void init_digraph() // инициализация мартицы смежности
{
    g.resize( N, std::vector< bool >( N, false ) );
}
 
void read_digraph() // считываем ребра орграфа: вводим пары чисел, обозначающих исходную и конечную вершины
{
    for ( int p, q; std::cin >> p >> q; ) // ctrl+Z для выхода
        if ( p >= 0 && p < N && q >= 0 && q < N && p != q )
            g[ p ][ q ] = true;
}
 
void show_digraph() // самая бестолковая функция
{
    for ( int i = 0; i < N; ++i )
    {
        for ( int j = 0; j < N; ++j )
            std::cout << g[ i ][ j ] << ' ';
        std::cout << std::endl;
    }
}
 
bool dfs( int i ) // самая важная функция: обход орграфа и поиск цикла
{
    pre[ i ] = true; // первый раз натыкаемся на вершину и сразу помечаем ее (прямой обход), дальше будем обходить ее потомков
    for ( int j = 0; j < N; ++j ) // побежали обходить потомков вершины i
    {
        if ( !g[ i ][ j ] ) continue; // нет ребра i->j
        if ( !pre[ j ] ) // в вершине j мы еще ни разу не были
        {
            if ( !dfs( j ) ) // обходим вершину j (и всех ее потомков)
                return false; // где-то в процессе обхода потомков вершины j нашли цикл (слышен крик из глубины) (как нашли смотри на пару строк ниже)
            post[ j ] = true; // еще раз помечаем вершину, но теперь все ее потомки обойдены и здесь нам делать нечего (обратный обход)
        }
        // слеующая строка самая главная, ради нее всё и затевалось, ради нее делались все пометки в векторах pre и post
        else if ( !post[ j ] ) // в вершине j мы уже были (т.к. pre[ j ] == true), но обошли не всех ее потомков - это и есть условие цикла (это сложно понять, но это так)
            return false; // кричим из глубины рекурсии, что цикл найден
    }
    return true; // крика не было, всё тихо, т.е. true
}
 
bool isDAG() // функция проверки на то, является ли орграф DAG-графом, т.е. орграфом, не содержащим циклов
{
    pre.resize( N, false ); // сбрасываем пометки
    post.resize( N, false ); // еще раз сбрасываем пометки 
    for ( int i = 0; i < N; ++i ) // этот for и следующий за ним if нужны для несвязных графов; если граф связный то можно обойтись только вызовом dfs( 0 )
        if ( !pre[ i ] ) // описал выше
            if ( !dfs( i ) ) // запуск проверки орграфа на циклы
                return false; // был найден цикл
    return true; // как мы не мучили орграф, но так и не смогли найти цикл
}
 
int main()
{
    std::cin >> N; // вводим кол-во вершин в орграфе
    init_digraph();
    read_digraph();
    show_digraph();
    if ( isDAG() )  // нет циклов
        std::cout << "DAG" << std::endl;
    else // есть циклы
        std::cout << "!DAG" << std::endl;
 
    return 0;
}