Cod sursa(job #1347310)

Utilizator stefantrettTrett Stefan stefantrett Data 18 februarie 2015 21:42:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <bitset>

#define inf 0x3f3f3f3f
#define nMax 5005
#define cost first
#define nod second

using namespace std;

vector <int> postordine;
vector <int> G[nMax];
bitset <nMax> viz;
int n, m;
int nrc;

void dsf(int k)
{
    viz[k] = 1;
    for(int i=0; i<G[k].size(); ++i)
        if(!viz[G[k][i]])
        {
            postordine.push_back(G[k][i]);
            dsf(G[k][i]);
        }
}

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<m;++i)
    {
        int a, b;
        scanf("%d %d\n", &a, &b);
        G[a].push_back(b);
    }
    postordine.push_back(1);
}

void sol()
{
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            nrc++;
            dsf(i);
        }
    }

}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    citire();
    sol();

    //cout<<nrc<<endl;
    for(int i=0;i<postordine.size();++i)
    {
        //cout<<postordine[i]<<endl;
        printf("%d ", postordine[i]);
    }
    return 0;
}