Pagini recente » Cod sursa (job #1634227) | Cod sursa (job #863538) | Cod sursa (job #2679236) | Cod sursa (job #1928983) | Cod sursa (job #1228644)
#include<iostream>
#include<list>
#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#define Nmax 50001
using namespace std;
int read(vector<int> G[])
{
int size, edges, x, y;
ifstream f("sortaret.in");
f>>size>>edges;
while(edges--)
{
f>>x>>y;
G[x].push_back(y);
}
return size;
}
void write(const list<int> &sol)
{
ofstream g("sortaret.out");
for(auto it = sol.begin(); it != sol.end(); ++it)
g<<*it<<" ";
g.close();
}
int main()
{
int size;
vector<int> G[Nmax];
int degree[Nmax];
size = read(G);
memset(degree, 0, sizeof(degree));
for(int i=1;i<=size;++i)
{
for(auto it = G[i].begin(); it != G[i].end(); ++it)
++degree[*it];
}
queue<int> Q;
list<int> sol;
for(int i=1;i<=size;++i)
if(degree[i] == 0)
Q.push(i);
while(!Q.empty()){
int vertex = Q.front();
Q.pop();
sol.push_back(vertex);
for(auto it = G[vertex].begin(); it != G[vertex].end(); ++it)
{
--degree[*it];
if(degree[*it] == 0)
Q.push(*it);
}
G[vertex].erase(G[vertex].begin(), G[vertex].end());
}
write(sol);
return 0;
}