Algoritmo de Kahn de ordenação topológica para resolver a questão ORKUT da OBI 2004.
Slides sobre ordenação topológica: https://docs.google.com/presentation/d/190PjxCX75m6VpJrNdR02j4yZJJPTGXl3OxQnrL_ON08/edit?usp=sharing
Link para a questão: https://www.thehuxley.com/problem/603
Código:
/*Rodrigo PaesExemplo do algoritmo de KAHN para ordenação topológica.Questão ORKUT - OBI 2004https://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érticeunordered_map<string, int> indexes;// Vértice para o nomevector<string> reverse_index;// Lista de adjancênciasvvi adj_list;// Conta quantas arestas chegam no vértice ivi indegree;// Verifica se o nó foi removido do grafo (remoção lógica)vector<bool> removed;// Resposta da ordenação topológicavi 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;}