Cod sursa(job #875973)

Utilizator dan.lincanDan Lincan dan.lincan Data 11 februarie 2013 03:52:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

void redirectInput(const char *in, const char *out)
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}

void printGraph(vector< vector<int> > &g, int n)
{
    for(int i = 0; i < (int) g.size(); ++i)
    {
        printf("%2d : ", i);
        for(int j = 0; j < (int) g[i].size(); ++j)
        {
            printf("%2d ", g[i][j]);
        }
        printf("\n");
    }
}

void printVector(vector<int> &v, int size)
{
    for(int i = 0; i < size; ++i)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

void solve()
{
    vector< vector<int> > graph;
    vector<int> incoming_edges;
    int n, m;
    scanf("%d %d", &n, &m);
    incoming_edges.resize(n, 0);
    graph.resize(n);
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        graph[x-1].push_back(y-1);
        ++incoming_edges[y-1];
    }
    queue<int> q;
    for(int i = 0; i < n; ++i)
    {
        if(incoming_edges[i] == 0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        printf("%d ", u + 1);
        for(int i = 0; i < graph[u].size(); ++i)
        {
            int v = graph[u][i];
            --incoming_edges[v];
            if(incoming_edges[v] == 0)
            {
                q.push(v);
            }
        }
    }
    printf("\n");
}

int main()
{
    redirectInput("sortaret.in", "sortaret.out");
    solve();
    return 0;
}