Pagini recente » Cod sursa (job #1947378) | Cod sursa (job #3221301) | Cod sursa (job #2407295) | Cod sursa (job #59589) | Cod sursa (job #2792511)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m,a,b,color[50001],dp[50001],afis[50001],nr;
vector <vector<int>> v(50001);
/*void dfs(int start)
{
stack <int> st;
st.push(start);
while (!st.empty())
{
int a=st.top(),ok=0;
if (dp[a]==0)
{
afis[nr]=a;
nr++;
}
dp[a]=1;
for (int j=0; j<v[a].size(); j++)
{
int next=v[a][j];
if (dp[next]==0)
{
ok=1;
st.push(next);
}
}
if (ok==0)
st.pop();
}
}*/
void dfs(int cur)
{
color[cur]=1;
for (int j=0; j<v[cur].size(); j++)
{
int next=v[cur][j];
if (color[next]==0)
{
dfs(next);
}
else if (color[next]==1) return;
}
color[cur]=2;
afis[nr]=cur;
nr++;
}
int main()
{
f>>n>>m;
for (int i=1; i<=m; i++)
{
f>>a>>b;
v[a].push_back(b);
}
for (int i=1; i<=n; i++)
{
if (color[i]==0)
{
dfs(i);
}
}
for (int i=nr-1; i>=0; i--)
{
g<<afis[i]<<' ';
}
return 0;
}