Pagini recente » Arhiva de probleme | Cod sursa (job #477556) | Cod sursa (job #1121645) | Solutii Winter Challenge 2008, Runda 1 | Cod sursa (job #2104089)
#include <bits/stdc++.h>
using namespace std;
int vertices, edges, u, v, degree[50001];
vector<int> adj[50001];
int main()
{
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d %d", &vertices, &edges);
for(int i = 1; i <= edges; i++)
{
scanf("%d %d", &u, &v);
adj[u].push_back(v);
degree[v]++;
}
stack<int> q;
for(int node = 1; node <= vertices; node++)
{
if(degree[node] == 0)
{
q.push(node);
}
}
while(!q.empty())
{
int current = q.top(); q.pop();
printf("%d ", current);
for(int child : adj[current])
{
if(--degree[child] == 0)
{
q.push(child);
}
}
}
return 0;
}
///Kahn's algorithm
///L ← Empty list that will contain the sorted elements
///S ← Set of all nodes with no incoming edge
///while S is non-empty do
/// remove a node n from S
/// add n to tail of L
/// for each node m with an edge e from n to m do
/// remove edge e from the graph
/// if m has no other incoming edges then
/// insert m into S
///if graph has edges then
/// return error (graph has at least one cycle)
///else
/// return L (a topologically sorted order)