Cod sursa(job #889580)

Utilizator RobertBBadea Corneliu Robert RobertB Data 24 februarie 2013 16:37:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
 
ifstream f("sortaret.in");
ofstream g("sortaret.out");
 
int N, M;
int grad[50010];
int sol[50010];
bool ver[50010];

vector<int> G[50010];
queue<int> coada;


vector<int>::iterator it;
 
int main ()
{
	int a, b;
	int k = 0;
    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        f >> a >> b;
        grad[b]++;
        G[a].push_back(b);
    }
    for (int i = 1; i <= N; i++) {
        if(grad[i]==0) {
            coada.push(i);
            ver[i]=1;
        }
	}
    while (!coada.empty())
    {
        a = coada.front();
        coada.pop();
		k++;
        sol[k] = a;
        for(it=G[a].begin(); it!=G[a].end(); it++) {
            if(!ver[*it]) {
                grad[*it]--;
                if(grad[*it] == 0)
                {
                    coada.push(*it);
                    ver[*it] = 1;
                }
            }
		}
    }
    for (int i=1; i<=N; i++) {
        g << sol[i] << " ";
	}
}