Cod sursa(job #990721)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 august 2013 22:59:41
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= n; ++j){
            if(degree[j] == 0 && !used[ j ]){
                printf("%d ",j);
                used[ j ] = 1;
                for(it=lv[j].begin();it!=lv[j].end();++it)
                    --degree[*it];
            }
        }
}

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

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