Pagini recente » Profil MadalinaJacksoon | Istoria paginii utilizator/spranceana_sonia | Istoria paginii utilizator/spranceana_sonia | Rating Tesileanu Alexandru (Teshy) | Cod sursa (job #1175008)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <forward_list>
using namespace std;
#define MAXNODES 50000
#define MAXEDGES 100000
int m, n, sorted_index;
forward_list<int> adj[MAXNODES];
int tsorted[MAXNODES];
bool visited[MAXNODES], has_neigh[MAXNODES];
void read_input()
{
string line;
ifstream myfile("sortaret.in");
if (myfile.is_open())
{
myfile >> n;
myfile >> m;
int i, from, to;
for (i = 0; i < m; ++i)
{
myfile >> from;
myfile >> to;
adj[from].push_front(to);
has_neigh[from] = true;
has_neigh[to] = true;
}
myfile.close();
sorted_index = n;
//for (i = 0; i < n; ++i)
//{
// cout << '\n' << i << ": ";
// for (int& x : adj[i])
// {
// cout << x << ' ';
// }
//}
}
}
void dfs(int node)
{
//cout << node << ' ';
for (int& x : adj[node])
{
if (!visited[x])
{
dfs(x);
}
}
visited[node] = true;
tsorted[--sorted_index] = node;
}
void resolve()
{
//cout << '\n' << "dfs: ";
for (int i = 1; i <= n; ++i)
{
if (has_neigh[i])
{
if (!visited[i] && !adj[i].empty())
{
dfs(i);
}
}
else
{
tsorted[--sorted_index] = i;
}
}
}
void print_solution()
{
ofstream fout("sortaret.out");
//cout << '\n' << "tsorted: ";
for (int i = 0; i < n; ++i)
{
fout << tsorted[i] << ' ';
}
}
int main()
{
read_input();
resolve();
print_solution();
//char x;
//cin >> x;
return 0;
}