Cod sursa(job #1718438)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 17 iunie 2016 20:44:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

int n, m;
vector<int> vecini[50500];
int grade[50500];

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &tmp1, &tmp2);
        tmp1--;
        tmp2--;

        vecini[tmp1].push_back(tmp2);
        grade[tmp2]++;
    }
}

bool exista()
{
    for(int i = 0; i < n; i++)
    {
        if(grade[i] != -1)
        {
            return true;
        }
    }

    return false;
}

void sortareTopologica()
{
    vector<int> tmp;

    while(exista())
    {
        for(int i = 0; i < n; i++)
        {
            if(grade[i] == 0)
            {
                printf("%d ", i + 1);
                grade[i] = -1;

                tmp.push_back(i);
            }
        }

        for(int i = 0; i < tmp.size(); i++)
        {
            for(int j = 0; j < vecini[tmp[i]].size(); j++)
            {
                grade[vecini[tmp[i]][j]]--;
            }
        }

        tmp.clear();
    }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    citire();
    sortareTopologica();

    return 0;
}