Cod sursa(job #2610492)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 mai 2020 22:27:11
Problema Componente tare conexe Scor 0
Compilator cpp-64 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[100003],d[100003];
 
struct nod
{
    int info;
    nod* urm;
}*pt[100003];
 
void InserareNod(nod* &point,int val)
{
    nod* cap = new nod;
    cap->info = val;
    cap->urm = point;
    point = cap;
}
 
void BF()
{
    u = p;
    p = 1;
 
    while( p <= u )
    {
        nod* cap = pt[C[p]];
 
        while( cap != NULL )
        {
            d[cap->info]--;
 
            if( d[cap->info] == 0 )
                C[++u] = cap->info;
 
            cap = cap->urm;
        }
        p++;
    }
    for(int i = 1 ; i <= N ; i++)
        g<<C[i]<<' ';
}
 
int main()
{
    int x,y;
    f>>N>>M;
 
    for(int i = 1 ; i <= N ; i++)
        pt[i] = NULL;
 
    for(int i = 1 ; i <= M ; i++)
    {
        f>>x>>y;
        InserareNod(pt[x],y);
        d[y]++;
    }
 
    for(int i = 1 ; i <= N ; i++)
    {
        if( d[i] == 0 )
            C[++p] = i;
    }
    BF();
 
    return 0 ;
}