Cod sursa(job #1725180)

Utilizator SilviuIIon Silviu SilviuI Data 5 iulie 2016 09:53:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>

#define nmax 100010
#define mod 1000000007
#define kmod 666013
#define lmod 100003
#define B 256
#define buffersize 32768

#define mp make_pair
#define pb push_back
#define F first
#define S second

using namespace std;

typedef pair <int,int> pii;
typedef long long int ll;
typedef short int si;

int n,m,x,y;
int l[nmax];
vector <int> g[nmax],sol;

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d %d",&n,&m);

    for (int i=1;i<=m;i++) {
        scanf("%d %d",&x,&y);
        g[x].pb(y); l[y]++;
    }

    queue <int> que;

    for (int i=1;i<=n;i++)
        if (l[i]==0) que.push(i);

    while (!que.empty()) {
        int x=que.front(); que.pop();
        sol.pb(x);
        for (int i=0;i<(int)g[x].size();i++) {
            l[g[x][i]]--;
            if (l[g[x][i]]==0) que.push(g[x][i]);
        }
    }

    for (int i=0;i<(int)sol.size();i++) printf("%d ",sol[i]);

    return 0;
}