Cod sursa(job #1109774)

Utilizator bia423Bianca Floriana bia423 Data 17 februarie 2014 16:14:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
# define nmax 50001
# define mmax 100001
vector<int>graf[nmax];
int n,m,coada[nmax],grd[nmax],ps=1,viz[nmax];
void bfs()
{ int i,pi=1;
    for(i=1;i<=n;i++)
    if(grd[i]==0){ coada[ps]=i; ps++; grd[i]=-1; out<<i<<" ";}
    while(pi<=ps)
    { for(i=0;i<graf[coada[pi]].size();i++)
            {   viz[graf[coada[pi]][i]]=1;
                coada[ps]=graf[coada[pi]][i]; grd[graf[coada[pi]][i]]--;
                ps++;
            } viz[coada[pi]]=1;


                for(i=1;i<=n;i++)
                if(grd[i]==0)
                {out<<i<<" ";grd[i]=-1;}
            pi++;
    }


}


int main()
{ int i,a,b,j;
    in>>n>>m;
    for(i=1;i<=m;i++)
    { in>>a>>b;
        graf[a].push_back(b);
        grd[b]++;
    }
bfs();
 for(j=1;j<=n;j++)
    {
     cout<<j<<" ";
    for(i=0;i<graf[j].size();i++)
        cout<<graf[j][i]<<" ";
        cout<<"\n"; }


    return 0;
}