Cod sursa(job #1087259)

Utilizator 96andreiFMI Andrei Barbu 96andrei Data 19 ianuarie 2014 09:25:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

const int N=50001;
vector<int> graph[N];
int grin[N];

ofstream fout("sortaret.out");


void dfs(int x)
{
    grin[x]=-1;
    fout<<x<<" ";

    vector<int>::iterator it;

    for(it=graph[x].begin() ; it!=graph[x].end(); it++)
    {
        grin[*it]--;
        if(grin[*it]==0)
            dfs(*it);
    }
    /*
    for(int i=0 ; i<graph[x].size(); i++)
    {
        grin[graph[x][i]]--;
        if(grin[graph[x][i]]==0)
            dfs(graph[x][i]);
    }
    */
}


int main()
{
    int x,y,n,m;
    ifstream fin("sortaret.in");
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        grin[y]++;
        graph[x].push_back(y);
    }
    for(int i=1; i<=n; i++)
      if(grin[i]==0)
        dfs(i);
    return 0;
}