Cod sursa(job #2419710)

Utilizator ZamfiAndreiZamfira Andrei ZamfiAndrei Data 9 mai 2019 11:51:19
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define MAXVertices 500

using namespace std;
vector<vector<int>> muchii(MAXVertices, vector<int>(MAXVertices));
vector<int> grad(MAXVertices);
vector<bool> vizitat;

void remove_grad(int i) {
    for (int j = 1; j <= muchii.size(); j++) {
        if (muchii[i][j] == 1) grad[j]--;
    }
}

int main()
{
    queue<int> grad0;
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int n, m, i, j, s = 0;
    vizitat.resize(n);
    f>>n>>m;
    for (i = 0; i < m; i++) {
        int m1, m2;
        f>>m1>>m2;
        muchii[m1][m2] = 1;
        grad[m2]++;
    }

    for (i = 1; i <= n; i++) {
        if (grad[i] == 0 && vizitat[i] == false) {
            vizitat[i] = true;
            grad0.push(i);
            remove_grad(i);
            g<<i<<" ";
            i = 1;
        }
    }

    return 0;
}