Cod sursa(job #3167154)

Utilizator dariustgameTimar Darius dariustgame Data 10 noiembrie 2023 10:32:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> graf[50001];
    vector<int> dependencies[50001];
    queue<int> st;
    bool fr[50001] = {false};
    bool visited[50001] = {false};
    for (int i = 0; i < prerequisites.size(); i++)
    {
        fr[prerequisites[i][0]] = true;
        graf[prerequisites[i][1]].push_back(prerequisites[i][0]);
        dependencies[prerequisites[i][0]].push_back(prerequisites[i][1]);
    }
    for (int i = 0; i < numCourses; i++)
    {
        if (!fr[i])
        {
            st.push(i);
            visited[i] = true;
        }
    }
    int currentNode;
    bool ok;
    while (!st.empty())
    {
        currentNode = st.front();
        st.pop();
        fout << currentNode + 1 << ' ';
        for (int i = 0; i < graf[currentNode].size(); i++)
        {
            if (visited[graf[currentNode][i]] == false)
            {
                ok = true;
                for (int j = 0; j < dependencies[graf[currentNode][i]].size(); j++)
                {
                    if (visited[dependencies[graf[currentNode][i]][j]] == 0)
                    {
                        ok = false;
                        break;
                    }
                }
                if (ok)
                {
                    visited[graf[currentNode][i]] = true;
                    st.push(graf[currentNode][i]);
                }
            }
        }
    }
}

int n, m, x, y;

int main()
{
    vector<vector<int>> dep;
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y;
        vector<int> aux;
        aux.push_back(y - 1);
        aux.push_back(x - 1);
        dep.push_back(aux);
    }
    canFinish(n, dep);
    return 0;
}