Pagini recente » Cod sursa (job #3142588) | Cod sursa (job #1970445) | Cod sursa (job #2131122) | Cod sursa (job #2606523) | Cod sursa (job #1970466)
#include <fstream>
#include <vector>
using namespace std;
struct graph{
vector<long int>* adj;
int s;
graph(const long int& sz)
{
s = sz;
adj = new vector<long int>[s];
}
long int size() const
{
return s;
}
void insert_edge(const long int& u, const long int& v)
{
adj[u].push_back(v);
}
};
vector<long int> sol;
bool b[50000];
void top_sort_util(graph& g, long int node)
{
b[node] = true;
sol.push_back(node);
for(unsigned long int i = 0; i < g.adj[node].size(); i++)
if(!b[g.adj[node][i]])
top_sort_util(g,g.adj[node][i]);
}
void top_sort(graph& g)
{
for(long int i = 0; i < g.size(); i++)
if(!b[i])
top_sort_util(g,i);
}
long int m, n;
int main()
{
ifstream f("sortaret.in");
ofstream g("sortaret.out");
f >> n >> m;
graph gr(n);
for(long int i = 0; i < m; i++)
{
long int u, v;
f >> u >> v;
u--;v--;
gr.insert_edge(u,v);
}
top_sort(gr);
for(unsigned long int i = 0; i < sol.size(); i++)
g << sol[i]+1 << ' ';
return 0;
}