Cod sursa(job #1110936)

Utilizator ThomasFMI Suditu Thomas Thomas Data 18 februarie 2014 15:02:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

#define NMax 50002

vector<int> gr[2*NMax];
#define gr (gr + NMax)

vector<int> v[NMax],w[NMax];
queue<int> cd;

int n,m;
int viz[NMax],grad[NMax];
int mn=1,mx=1;

void bf(int s)
{
    int i,e;

    cd.push(s);
    viz[s]=1;
    grad[s]=1;
    gr[1].push_back(s);

    while(!cd.empty())
    {
        s=cd.front();
        cd.pop();
        e=v[s].size();
        for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
        {
            cd.push(v[s].at(i));
            viz[v[s].at(i)]=1;
            grad[v[s].at(i)]=grad[s]+w[s].at(i);
            gr[grad[v[s].at(i)]].push_back(v[s].at(i));

            if(grad[v[s].at(i)]<mn) mn=grad[v[s].at(i)];
            if(grad[v[s].at(i)]>mx) mx=grad[v[s].at(i)];
        }
    }
}

int main()
{
    int i,a,b;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        w[a].push_back(1);
        v[b].push_back(a);
        w[b].push_back(-1);
    }

    for(i=1;i<=n;i++) if(viz[i]==0) bf(i);

    for(i=mn;i<=mx;i++)
    {
        b=gr[i].size();
        for(a=0;a<b;a++) g<<gr[i].at(a)<<" ";
    }

    g<<"\n";

    f.close();
    g.close();
    return 0;
}