Cod sursa(job #470141)

Utilizator bugyBogdan Vlad bugy Data 11 iulie 2010 17:07:52
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
//#include<cstring>
#include <vector>
using namespace std;
#define dim 50010
#define pb push_back

int N, M, viz[dim], deg[dim], i, j, k,a,b;
vector<int> G[dim];

FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");

void solve()
{
    for(i = 1; i <= N; i++)
    {
        for(j = 1; j <= N; j++)
		if(!viz[j] && deg[j] == 0)
         {
          viz[j] = 1, fprintf(g,"%d ", j);
          for(k = 0; k < G[j].size(); k++)
				deg[ G[j][k] ]--;
            break ;
         }
    }
	fprintf(g,"\n");
}

void citire()
{
    fscanf(f,"%d %d\n", &N, &M);
    for(i = 1; i <= M; i++)
        fscanf(f,"%d %d", &a, &b), G[a].pb(b), deg[b]++;
}

int main()
{
    citire();
    solve();
	
fclose(f);
fclose(g);

    return 0;
}