Cod sursa(job #609555)

Utilizator alinhAlin H alinh Data 22 august 2011 10:56:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;

#define MAX 50010

ifstream fi;
ofstream fo;

int n;
int m;
int grad[MAX];
int s;
int sol[MAX];
vector<int> g[MAX];


int main()
{
    // citire
    fi.open("sortaret.in");
    fi >> n >> m;
    for (int i=1; i<=n; i++)
        grad[i] = 0;
    for (int i=1; i<=m; i++)
    {
        int a,b;
        fi >> a >> b;
        g[a].push_back(b);
        ++grad[b];
    }
    fi.close();

    // parcurgere
    s = 0;
    for (int i=1; i<=n; i++)
        if (grad[i] == 0)
        {
            sol[++s] = i;
        }

    vector<int>::iterator it;

    for (int i=1; i<=n; i++)
    {
        int b = sol[i];

        for (it = g[b].begin(); it != g[b].end(); ++it)
        {
            int c = *it;
            --grad[*it];
            if (grad[*it] == 0)
                sol[++s] = *it;
        }
    }

    // tiparire
    fo.open("sortaret.out");
    for (int i=1; i<=s; i++)
        fo << sol[i] << " ";
    fo.close();
    return 0;
}