Pagini recente » Cod sursa (job #336955) | Cod sursa (job #2966133) | Cod sursa (job #540307) | Cod sursa (job #2157608) | Cod sursa (job #2660420)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int main()
{
int N, M, x1, x2;
in >> N >> M;
vector<vector<int>> adj(N + 1); //listele de adiacenta
vector<int> deg(N + 1, 0); // gradele nodurilor
vector<int> q; // folosesc un vector drept coada pentru sortarea topologica
for (int i = 0; i < M; ++i)
{
in >> x1 >> x2;
adj[x1].push_back(x2); //adaug muchie in lista
}
// aflu gradul initial al fiecarui nod
for (int i = 1; i <= N; ++i)
for (auto j : adj[i])
++deg[j];
int first = 0, last = 0;
for (int i = 1; i <= N; ++i)
if (deg[i] == 0)
{
q.push_back(i); // daca un nod are gradul 0 il adaug in coada
++last;
}
while(first <= last)
{
int node = q[first];
++first;
for (int nbh : adj[node])
{
--deg[nbh];
if (deg[nbh] == 0)
{
q.push_back(nbh);
++last;
}
}
}
for ( int i = 0; i < last; ++i)
out << q[i] <<" ";
return 0;
}