Pagini recente » Diferente pentru schimbare-borland/alternativa intre reviziile 7 si 14 | Atasamentele paginii Clasament rar41 | Cod sursa (job #1192709) | Cod sursa (job #911009) | Cod sursa (job #1175000)
#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], nodes[MAXNODES], nr_of_added_nodes;
bool visited[MAXNODES];
int add_node(int node)
{
for (int i = 0; i < nr_of_added_nodes; i++)
{
if (nodes[i] == node)
return i;
}
nodes[nr_of_added_nodes++] = node;
return nr_of_added_nodes - 1;
}
void read_input()
{
string line;
ifstream myfile("sortaret.in");
if (myfile.is_open())
{
myfile >> n;
myfile >> m;
int i, from, to, from_index, to_index;
for (i = 0; i < m; ++i)
{
myfile >> from;
myfile >> to;
from_index = add_node(from);
to_index = add_node(to);
adj[from_index].push_front(to_index);
//cout << a[i - 1] << ' ';
}
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_index)
{
//cout << node << ' ';
for (int& x : adj[node_index])
{
if (!visited[x])
{
dfs(x);
}
}
visited[node_index] = true;
tsorted[--sorted_index] = nodes[node_index];
}
void resolve()
{
//cout << '\n' << "dfs: ";
dfs(0);
}
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;
}