Cod sursa(job #2789277)

Utilizator mihneadv@yahoo.comDavid Mihnea Stefan [email protected] Data 27 octombrie 2021 11:58:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

vector<vector<int>>v;
vector<int>gradInt;
int X;

void solve()
{
    queue<int>Q;
    for(int i = 0; i < X; i++)
    {
        if(gradInt[i] == false)
        {
            cout << i + 1 << ' ';
            Q.push(i);
        }
    }
    while(!Q.empty())
    {
        int actual = Q.front();
        Q.pop();
        for(int i = 0; i < v[actual].size(); i++)
        {
            gradInt[v[actual][i]]--;
            if(gradInt[v[actual][i]] == false)
            {
                cout << v[actual][i] + 1 << " ";
                Q.push(v[actual][i]);
            }
        }
    }

}

int main() {
    int U;
    cin >> X >> U;
    v.resize(X);
    gradInt.resize(X);
    for (int i = 0; i < U; i++) {
        int V1, V2;
        cin >> V1 >> V2;
        V1--, V2--;
        v[V1].push_back(V2);
        gradInt[V2]++;
    }
    solve();
    return false;
}