Cod sursa(job #1734889)

Utilizator deepsterescuCraciunescu Denis Bogdan deepsterescu Data 28 iulie 2016 14:27:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 50005
using namespace std;

int n,m;
vector<int> graf[NMAX];

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graf[x].push_back(y);
    }
}
int viz[NMAX];
stack<int> s;
void dfs(int c)
{
    viz[c]=1;
    for(vector<int>::iterator ii = graf[c].begin();ii!=graf[c].end(); ii++)
        if(!viz[*ii])
            dfs(*ii);
    s.push(c);
}

void sort()
{
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    while(!s.empty())
    {
        printf("%d ",s.top());
        s.pop();
    }
}

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

    return 0;
}