Cod sursa(job #1441133)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 23 mai 2015 19:01:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <vector>
#define Max 50001
using namespace std;

vector <int> G[Max];
int N,Sol[Max],nr;
char V[Max];

void Read()
{
    int X,Y,M;

    freopen("sortaret.in","r",stdin);
    scanf("%d %d",&N,&M);
    while(M--)
    {
        scanf("%d %d",&X,&Y);
        G[X].push_back(Y);
    }
}

void DFS(int x)
{
    vector<int>::iterator i;
    V[x] = 1;
    for (i=G[x].begin();i!=G[x].end();i++)
        if (!V[*i]) DFS(*i);
    Sol[nr++]=x;
}

void Write()
{
    freopen("sortaret.out","w",stdout);
    while(N--)
    {
        printf("%d ",Sol[N]);
    }
    printf("\n");
}

void Solve()
{
    for (int i=1;i<=N;i++)
        if(!V[i]) DFS(i);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}