Pagini recente » Cod sursa (job #1217838) | Cod sursa (job #2629554) | Rating Baciu RAdu (orange) | Istoria paginii runda/cerculetz_01/clasament | Cod sursa (job #1698658)
#include <iostream>
#include <fstream>
using namespace std;
struct NodeList
{
unsigned int info;
NodeList *next;
};
struct List
{
NodeList *first;
NodeList *last;
};
void pushBack(List &l, unsigned int value)
{
NodeList *p = new NodeList;
p->info = value;
p->next = NULL;
if (l.first == NULL) {
l.first = l.last = p;
}
else
{
l.last->next = p;
l.last = p;
}
}
void pushFront(List &l, unsigned int value)
{
NodeList *p = new NodeList;
p->info = value;
if (l.first == NULL)
{
p->next = NULL;
l.first = l.last = p;
}
else
{
p->next = l.first;
l.first = p;
}
}
List order;
void DFS(List *link, bool *visited, unsigned int nodeTag)
{
visited[nodeTag] = true;
NodeList *p = link[nodeTag].first;
while (p)
{
if (!visited[p->info]) {
DFS(link, visited, p->info);
}
p = p->next;
}
pushFront(order, nodeTag);
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
unsigned int n, m, x, y;
fin >> n >> m;
List *link = new List[n + 1];
bool *visited = new bool[n + 1];
for (unsigned int i = 1; i <= n; ++i)
{
link[i].first = link[i].last = NULL;
visited[i] = false;
}
order.first = order.last = NULL;
while (m)
{
fin >> x >> y;
pushBack(link[x], y);
--m;
}
for (unsigned int i = 1; i <= n; ++i)
{
if (!visited[i]) {
DFS(link, visited, i);
}
}
NodeList *p = order.first;
while (p)
{
fout << p->info << ' ';
p = p->next;
}
fin.close();
fout.close();
return 0;
}