Cod sursa(job #990726)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 august 2013 23:05:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

#define x first
#define y second

using namespace std;

int used[50001],n,m,degree[50001];
vector<int> lv[50001];
pair <int,int> vertx[200000];

void get_Data()
{
    scanf("%d%d",&n,&m);
    int x,y,i;
    for(i = 1; i <= m; ++i){
        scanf("%d%d", &x, &y);
        vertx[ i ] = make_pair(x,y);
    }
    sort(vertx+1,vertx+m+1);
        for(i = 1; i <= m; ++i)
        if(vertx[ i ].x != vertx[ i ].y &&
            (vertx[ i - 1 ].x != vertx[ i ].x || vertx[ i - 1 ].y != vertx[ i ].y)){
           lv[vertx[i].x].push_back(vertx[i].y);
           ++degree[vertx[i].y];
        }
}

void Topological()
{
    int i,j;
    vector<int> ::iterator it;
    queue <int> Q;
    for(i = 1; i <= n; ++i)
        if(!degree[ i ])
            Q.push( i );
    while(!Q.empty()){
        j = Q.front();Q.pop();
        printf("%d ",j);
        used[ j ] = 1;
        for(it = lv[j].begin(); it != lv[ j ].end(); ++it){
            --degree[ *it ];
            if(degree[ *it ] == 0 && !used[ *it ])
                    Q.push( *it );
        }
    }
}


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

    get_Data();
    Topological();
    return 0;
}