Pagini recente » Cod sursa (job #181652) | Cod sursa (job #567320) | Cod sursa (job #2439927) | Cod sursa (job #2747271) | Cod sursa (job #1709165)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
int main()
{
int NrVertex,NrEdges;
vector<list<int>> edges;
list<int> freeEdges;
list<int> sortedVertex;
vector<int> gradInterior;
ifstream in("sortaret.in");
in>>NrVertex>>NrEdges;
edges.assign(NrVertex+1,list<int>());
gradInterior.assign(NrVertex+1,0);
for(int i=0; i<NrEdges; i++)
{
int x,y;
in>>x>>y;
edges[x].push_back(y);
gradInterior[y]++;
}
in.close();
for(int i=1; i<NrVertex+1; i++)
if(gradInterior[i]==0)
freeEdges.push_back(i);
while(freeEdges.empty()==0)
{
int x,y;
x = freeEdges.front();
freeEdges.pop_front();
sortedVertex.push_back(x);
while(edges[x].empty()==0)
{
y=edges[x].front();
edges[x].pop_front();
gradInterior[y]--;
if(gradInterior[y]==0)
freeEdges.push_back(y);
}
}
ofstream out("sortaret.out");
for(list<int>::iterator i=sortedVertex.begin(); i!=sortedVertex.end(); i++)
out<<*i<<" ";
out.close();
return 0;
}