Cod sursa(job #1995770)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 29 iunie 2017 04:17:31
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N,M;
int p,u,C[1000000];

bool viz[1000000];

vector <int> v[1000000];

void BF()
{
    u = p;
    while( p <= u )
    {
        vector<int>::const_iterator p1;
        if( v[C[p]].size() != 0 )
        for(p1 = v[C[p]].begin() ; p1 != v[C[p]].end() ; p1++)
        {
            if( viz[*p1] == false )
            {
                viz[*p1] = true;
                C[++u] = *p1;
            }
        }
        p++;
    }
    for(int i = 1 ; i <= N ; i++)
        g<<C[i]<<' ';
}

int main()
{
    int x,y;
    f>>N>>M;
    for(int i = 1 ; i <= M ; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        viz[y] = true;
    }
    for(int i = 1 ; i <= N ; i++)
    {
        if( viz[i] == false )
        {
            viz[i] = true;
            C[++p] = i;
        }
        else
            viz[i] = false;
    }
    BF();
    return 0 ;
}