Pagini recente » Cod sursa (job #303474) | Cod sursa (job #1104646) | Cod sursa (job #693547) | Cod sursa (job #2875635) | Cod sursa (job #3297128)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
vector<vector<int> > v, vt;
stack<int> s;
int cnt;
int viz[100001], viz2[100001];
void dfs(int nod)
{
viz[nod] = 1;
for(int i = 0; i<v[nod].size(); i++)
{
int vecin = v[nod][i];
if(!viz[vecin]) dfs(vecin);
}
s.push(nod);
}
void dfs2(int nod)
{
viz2[nod] = cnt;
for(int i = 0; i < vt[nod].size(); i++)
{
int vecin = vt[nod][i];
if(!viz2[vecin])
dfs2(vecin);
}
}
void dfs3(int nod)
{
viz[nod] = 1;
for(int i = 0; i<v[nod].size();i++)
{
int vecin = v[nod][i];
if(!viz[vecin]) dfs3(vecin);
}
s.push(nod);
}
int main()
{
int n, m;
fin >> n >> m;
v.resize(n+1);
for(int i = 1; i<=m; i++)
{
int a, b;
fin >> a >> b;
v[a].push_back(b);
}
for(int i = 1; i<=n; i++)
if(!viz[i])dfs3(i);
while(!s.empty())
{
fout << s.top() << ' ';
s.pop();
}
/*int n, m;
cin>> n >> m;
v.resize(n+1);
vt.resize(n+1);
for(int i = 1; i<=m; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
vt[b].push_back(a);
}
dfs(1);
while(!s.empty())
{
int nod = s.top();
s.pop();
if(!viz2[nod])
{
cnt++;
dfs2(nod);
}
}
cout << cnt << '\n';
for(int i = 1; i<=n; i++)
{
cout << viz2[i] << ' ';
}*/
return 0;
}