Pagini recente » Cod sursa (job #1365430) | Cod sursa (job #2735016) | Cod sursa (job #1836525) | Cod sursa (job #1427033) | Cod sursa (job #2423899)
#include <iostream>
#include <fstream>
#include <vector>
#include<set>
using namespace std;
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");
int main()
{
int n,m,x,y;
f>>n>>m;
vector<vector<int>>G(n+1);
vector<int> grdint(n+1,0);
set<pair<int,int>> Q;
vector<int> sortaret;
for (int i=0;i<m;i++)
{
f>>x>>y;
G[x].push_back(y);
grdint[y]++;
}
for (int i=1;i<=n;i++)
Q.insert(make_pair(grdint[i],i));
while (!Q.empty())
{
int nod=Q.begin()->second;
int grd=Q.begin()->first;
Q.erase(Q.begin());
if (grd!=0)
{
g<<"Nu se poate efectua sortarea topologica pentru ca graful are cicluri!";
return -1;
}
for (auto vecin:G[nod])
{
Q.erase(make_pair(grdint[vecin],vecin));
grdint[vecin]--;
Q.insert(make_pair(grdint[vecin],vecin));
}
sortaret.push_back(nod);
}
for (int i=0;i<n;i++)
g<<sortaret[i]<<" ";
}