Ordenação topológica - Kahn

Algoritmo de Kahn de ordenação topológica para resolver a questão ORKUT da OBI 2004.

Código:

/*

Rodrigo Paes

Exemplo do algoritmo de KAHN para ordenação topológica.

Questão ORKUT - OBI 2004

https://www.thehuxley.com/problem/603

*/

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

typedef vector<vi> vvi;

// Mapa do nome da pessoa para o vértice

unordered_map<string, int> indexes;

// Vértice para o nome

vector<string> reverse_index;

// Lista de adjancências

vvi adj_list;

// Conta quantas arestas chegam no vértice i

vi indegree;

// Verifica se o nó foi removido do grafo (remoção lógica)

vector<bool> removed;

// Resposta da ordenação topológica

vi top_order;

/*

Retorna verdadeiro caso tenha conseguido encontrar uma ordenação topológica.

Nesse caso, a resposta está em top_order

*/

bool top_sort()

    queue<int> q;

    int u;

/*

    Adiciona na fila todos os vértices que não possuem

    nenhuma aresta chegando nele.

*/

    for (int i=0; i< adj_list.size(); ++i)

        if (indegree[i] == 0 )

            q.push(i);

    while (!q.empty())

        u = q.front(); q.pop();

/*

        Se esse nó estava na fila, então nenhuma aresta chegava nele.

        O que significa que ele não depende mais de ninguém e, portanto,

        é parte da ordenação.

*/

        top_order.push_back(u);

        /* Marca o nó como removido do grafo */

        removed[u] = true;

/*

        Se o nó foi removido, para cada nó adjacente precisamos

        diminuir 1 do contador de arestas que chegam nesse nó adjacente, afinal,

        o nó não existe mais.

*/

        for (int k=0; k<adj_list[u].size(); ++k)

            int v = adj_list[u][k];

/*

            Caso o nó adjancente não tenha sido removido, então subtraímos 1 do contador

            de arestas. Caso o nó adjacente fique com 0 arestas, significa que ele agora

            será um candidato a ser colocado na fila, e o processo se repetirá.

*/

            if (!removed[v]  && --indegree[v] == 0)

                q.push(v);

    /* Se ao final do processo, todos os nós foram adicionados na em top_order,

    então significa que todos os elementos foram para a fila, o que significa

    que todas as pendências anteriores a ele foram satisfeitas e, portanto,

    encontramos uma ordem.

*/

    return adj_list.size() == top_order.size();

void clear_all(int n)

    indexes.clear();

    reverse_index.clear();

    adj_list.clear();

    adj_list.resize(n);

    indegree.clear();

    indegree.resize(n,0);

    removed.clear();

    removed.resize(n, false);

    top_order.clear();

int main()

    int n;

    string name;

    string source, target;

    int k, u, v;

    int test_case = 1;

    cin >> n;

    while (n)

        clear_all(n);

        for (int i=0; i<n; ++i)

            cin >> name;

            indexes[name] = i;

            reverse_index.push_back(name);

        for (int i=0; i<n; ++i)

            cin >> target >> k;

            v = indexes[target];

            for (int j=0; j< k; ++j)

                cin >> source;

                u = indexes[source];

                indegree[v]++;

                adj_list[u].push_back(v);

        cout << "Teste "<< test_case++ << endl;

        if (top_sort())

            for (int i=0; i<top_order.size(); ++i)

                if (i!=0)

                    printf(" ");

                cout << reverse_index[top_order[i]];

            printf("\n");

        else

            printf("impossivel\n");

        cin >> n;

        if (n) cout << endl;

    return 0;