Cod sursa(job #875974)

Utilizator dan.lincanDan Lincan dan.lincan Data 11 februarie 2013 04:04:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 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 dfs(int u,
    vector<vector<int> > &graph,
    vector<bool> &visited)
{
    if(visited[u])
        return;
    for(int i = 0; i < graph[u].size(); ++i)
    {
        int v = graph[u][i];
        dfs(v, graph, visited);
    }
    visited[u] = true;
    printf("%d ", u);
}

void dfs_based()
{
    vector< vector<int> > graph;
    vector<bool> visited;
    int n, m;
    scanf("%d %d", &n, &m);
    graph.resize(n);
    visited.resize(n, false);
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        graph[x-1][y-1];
    }
    for(int i = 0; i < n; ++i)
    {
        if(!visited[i])
            dfs(i, graph, visited);
    }
    printf("\n");
}

void Kahn()
{
    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");
    //Kahn();
    dfs_based();
    return 0;
}