Cod sursa(job #1112675)

Utilizator a96tudorAvram Tudor a96tudor Data 19 februarie 2014 22:27:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
#include<queue>
#include<vector>
#define pb push_back
#define N_MAX 50010
using namespace std;
vector <int> G[N_MAX];
queue <int> Q;
bool use[N_MAX];
int N,deg[N_MAX];
inline void BFS()
{
    if (Q.empty()) return;
    int Nod=Q.front();
    printf("%d ",Nod);
    for (vector <int> :: iterator it=G[Nod].begin();it!=G[Nod].end();++it)
    {
        deg[*it]--;
        if (!use[*it] && deg[*it]==0) {use[*it]=true; Q.push(*it);}
    }
    Q.pop();
    BFS();
}
inline void Load_Data()
{
    int M,x,y;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;++i) {scanf("%d%d",&x,&y); G[x].pb(y); deg[y]++;}
    for (int i=1;i<=N;++i) use[i]=false;
    for (int i=1;i<=N;++i)
        if (deg[i]==0) {Q.push(i); use[i]=true;}
}
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    Load_Data();
    BFS();
    printf("\n");
    fclose(stdin); fclose(stdout);
    return 0;
}