Pagini recente » Cod sursa (job #1935720) | Cod sursa (job #1198378) | Cod sursa (job #1956199) | Cod sursa (job #2363109) | Cod sursa (job #3224813)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <forward_list>
#include <stack>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void dfs(int start, vector<forward_list<int>> &adjacent, forward_list<int> &sorted, vector<bool> &visited);
int main()
{
int n, m;
forward_list<int> sorted;
vector<forward_list<int>> adjacent;
fin >> n >> m;
adjacent.resize(n);
for(int i = 0; i < n; i++)
{
int l, r;
fin >> l >> r;
l--;
r--;
adjacent[l].push_front(r);
}
vector<bool> visited(n, false);
for(int node = 0; node < n; node++)
{
if(!visited[node])
{
dfs(node, adjacent, sorted, visited);
}
}
for(auto &e : sorted)
{
fout << e + 1 << ' ';
}
return 0;
}
void dfs(int start, vector<forward_list<int>> &adjacent, forward_list<int> &sorted, vector<bool> &visited)
{
stack<int> next;
int node;
bool br;
next.push(start);
visited[start] = true;
while(!next.empty())
{
node = next.top();
br = false;
for(auto &neighbor : adjacent[node])
{
if(!visited[neighbor])
{
visited[neighbor] = true;
next.push(neighbor);
br = true;
break;
}
}
if(br)
continue;
sorted.push_front(node);
next.pop();
}
}