Cod sursa(job #1061812)

Utilizator RarRaresNedelcu Rares RarRares Data 20 decembrie 2013 12:21:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define nmax 50005

using namespace std;

int n, m;
vector<int> graf[nmax];
queue<int> coada;
int grad_int[nmax];

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d %d\n", &x, &y);

        graf[x].push_back(y);
        grad_int[y]++;
    }
}




void sortaret()
{
    for(int i = 1; i <= n; i++)
        if(grad_int[i] == 0)
            coada.push(i);

    while(!coada.empty())
    {
        int x = coada.front();
        coada.pop();
        cout << x << ' ';
        for(vector<int>::iterator it = graf[x].begin(); it != graf[x].end(); ++it)
        {
            grad_int[*it]--;
            if(grad_int[*it] == 0)
                coada.push(*it);
        }
    }
}




/**METODA 2: PRIN PARCURGERE IN ADANCIME*/
bool viz[nmax];
int sol[nmax];
int l = 0;
void adancime(int k)
{
    viz[k] = true;
    vector<int>::iterator it;
    for(it = graf[k].begin(); it != graf[k].end(); ++it)
        if(!viz[*it])
        {
            adancime(*it);
        }
    sol[++l] = k;
}

void afisare2()
{
    for(int i = n; i > 0; i--)
        cout << sol[i] << ' ';
}


void sortaret2()
{
    for(int i = 1; i <= n; i++)
    if(!viz[i])
    {
        adancime(i);
    }

    afisare2();
}



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

    citire();
//    sortaret();
    sortaret2();
    return 0;
}