Pagini recente » Cod sursa (job #561530) | Cod sursa (job #616599) | Cod sursa (job #752546) | Cod sursa (job #3286241) | Cod sursa (job #2031148)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graph
{
vector<vector<int>> adj;
vector<int> in_count;
public:
Graph(int n) : adj(n, vector<int>()), in_count(n, 0){}
void AddEdge(int u, int v)
{
adj[u].push_back(v);
in_count[v]++;
}
void PrintTopologicalSorting()
{
queue<int> q;
for (int i = 0; i < in_count.size(); i++)
{
if (!in_count[i])
{
q.push(i);
}
}
while (!q.empty())
{
int node = q.front();
q.pop();
out << node + 1 << ' ';
for (int i = 0; i < adj[node].size(); i++)
{
int v = adj[node][i];
in_count[v]--;
if (!in_count[v])
q.push(v);
}
}
}
};
int main()
{
int N, M;
in >> N >> M;
Graph g(N);
for (int i = 0; i < M; i++)
{
int u, v;
in >> u >> v;
u--; v--;
g.AddEdge(u, v);
}
g.PrintTopologicalSorting();
}