main:
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include "Graph.h"
using namespace std;

int main() {
    try {
        setlocale(LC_ALL, "");
        cout << "Введите имя файла: ";
        string filename;
        cin >> filename;
        ifstream in(filename);
        if (!in.is_open()) {
            throw invalid_argument("file error");
        }
        if (in.peek() == ifstream::traits_type::eof()) {
            throw invalid_argument("empty file");
        }
        int vertexCount;
        in >> vertexCount;
        if (!in || vertexCount < 1) {
            throw invalid_argument("количество вершин - натуральное число");
        }
        Graph a(vertexCount);
        in >> a;
        cout << "Топологически отсортированные вершины: \n";
        vector<int> topSort = topologicalSort(a);
        for (auto & v : topSort) {
            cout << v << ' ';
        }
        cout << "\nМинимальное остовное дерево: \n";
        cout << minOstov(a);
    }
    catch (invalid_argument &error) {
        cerr << error.what() << '\n';
        system("pause");
        return -1;
    }
    system("pause");
    return 0;
}


Graph.h
#pragma once
#include <vector>
using namespace std;
class Graph
{
private:
    vector<vector<int> > list_;
    vector<vector<int> > table_;
    // dfs
    vector<bool> used_; // вектор, показывающий, была ли посещена вершина
    vector<int> p_; // вектор, показывающий номер предка i-й вершины
    vector<int> d_; // вектор, показывающий время входа в i-ю вершину
    vector<int> f_; // вектор, показывающий время выхода в i-ю вершину
    bool oriented_; // флаг, показывающий, ялвяется ли граф ориентированным
    int time_;
    int size_;
public:
    Graph();
    Graph(const int &vertexCount);
    void addEdge(const int &from, const int &to, const int &wt);
    friend void dfs(Graph &a);
    friend void dfsVisit(Graph &a, const int & u);
    friend vector<int> topologicalSort(Graph &a);
    friend vector<vector<int> > scc(const Graph &a);
    friend Graph minOstov(const Graph &a);
    friend istream& operator>>(istream& in, Graph &a);
    friend ostream& operator<<(ostream& out, Graph a);
    ~Graph();
};

Graph.cpp
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <cassert>
using namespace std;


Graph::Graph() {
    size_ = 0;
    time_ = 0;
    oriented_ = false;
}

Graph::Graph(const int &vertexCount) {
    size_ = vertexCount;
    used_.resize(vertexCount, false);
    p_.resize(vertexCount, -1);
    d_.resize(vertexCount);
    f_.resize(vertexCount);
    time_ = 0;
    oriented_ = false;
    list_.resize(vertexCount);
    table_.resize(vertexCount, vector<int>(vertexCount));
}

void Graph::addEdge(const int &from, const int &to, const int &wt) {
    table_[from][to] = wt;
    if (wt != 0) {
        list_[from].emplace_back(to);
    }
}

Graph::~Graph()
{
}

void dfs(Graph &a) {
    for (int u = 0; u < a.size_; ++u) {
        if (!a.used_[u]) {
            dfsVisit(a, u);
        }
    }
}

void dfsVisit(Graph &a, const int &u) {
    a.time_++;
    a.d_[u] = a.time_;
    a.used_[u] = true;
    for (auto v : a.list_[u]) {
        if (!a.used_[v]) {
            a.p_[v] = u;
            dfsVisit(a, v);
        }
    }
    a.time_++;
    a.f_[u] = a.time_;
}

vector<int> topologicalSort(Graph &a) {
    dfs(a);
    vector<pair<int, int>> unsorted;
    for (int i = 0; i < a.size_; ++i){
        unsorted.push_back({ a.f_[i], i });
    }
    sort(unsorted.begin(), unsorted.end(), greater<pair<int, int>>());
    vector<int> sorted;
    for (int i = 0; i < a.size_; ++i) {
        sorted.push_back(unsorted[i].second);
    }
    return sorted;
}

Graph minOstov(const Graph &a) {
    if (a.oriented_) {
        throw invalid_argument("Граф должен быть неориентированным");
    }
    Graph tree(a.size_);
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < a.size_; ++i) {
        for (int j = i; j < a.size_; ++j) {
            if (a.table_[i][j]) {
                edges.push_back({ a.table_[i][j], { i, j } });
            }
        }
    }
    sort(edges.begin(), edges.end());
    vector<int> parent(a.size_, -1);
    function<int(int)> getRoot = [&](int v) {
        if (parent[v] < 0) {
            return v;
        }
        else {
            return parent[v] = getRoot(parent[v]);
        }
    };
    function<bool(int, int)> unite = [&](int u, int v) {
        u = getRoot(u);
        v = getRoot(v);
        if (u == v) {
            return false;
        }
        assert(parent[u] < 0);
        assert(parent[v] < 0);
        if (parent[u] < parent[v]) {
            parent[u] += parent[v];
            parent[v] = u;
        }
        else {
            parent[v] += parent[u];
            parent[u] = v;
        }
        return true;
    };
    for (auto const &edge : edges) {
        int wt = edge.first;
        int from = edge.second.first;
        int to = edge.second.second;
        if (unite(from, to)) {
            tree.addEdge(from, to, wt);
            tree.addEdge(to, from, wt);
        }
    }
    return tree;
}

istream& operator>>(istream& in, Graph &a) {
    for (int i = 0; i < a.size_; ++i) {
        for (int j = 0; j < a.size_; ++j) {
            int wt;
            in >> wt;
            if (!in || a.table_[i][j] < 0) {
                throw "нада 0+";
            }
            a.addEdge(i, j, wt);
        }
    }
    a.oriented_ = false;
    for (int i = 0; i < a.size_ && a.oriented_ != true; ++i) {
        for (int j = 0; j < a.size_ && a.oriented_ != true; ++j) {
            if (a.table_[i][j] != a.table_[j][i]) {
                a.oriented_ = true;
            }
        }
    }
    return in;
}

ostream& operator<<(ostream& out, Graph a) {
    for (int i = 0; i < a.size_; ++i) {
        for (int j = (a.oriented_)? 0 : i; j < a.size_; ++j) {
            if (a.table_[i][j]) {
                cout << "Ребро: " << i << " -> " << j << ". Вес: " << a.table_[i][j] << '\n';
            }
        }
    }
    return out;
}