Cod sursa(job #2105159)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 12 ianuarie 2018 18:54:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
//sortare topologica
#include<bits/stdc++.h>
#define N 50100
using namespace std;

int n,m,grad[N],q[N];
bool viz[N];
vector<int> G[N];

void read()
{
    int i,x,y;
    freopen("sortaret.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {scanf("%d%d",&x,&y);
    G[x].push_back(y);
    grad[y]++;
    }
}

void dfs()
{
    int i,j,k,nod,vf=0,x;
    vector<int>::iterator it;
    freopen("sortaret.out","w",stdout);
    //adaug nodul "1"
    for(x = 1; x <= n; x++)
     if(grad[x] == 0) q[++vf] = x;

    for(i = 1; i <= vf; i++)
    {
        x = q[i];
        for(it = G[x].begin(); it != G[x].end(); ++it)
        {
            grad[*it]--;
            if(grad[*it] == 0) q[++vf] = *it;
        }
    }
    for(i=1;i<=vf;i++) cout<<q[i]<<' ';


}

int main()
{
    read();
    dfs();
}