Pagini recente » Cod sursa (job #2404894) | Cod sursa (job #3122993) | Cod sursa (job #1433465) | Cod sursa (job #2058316) | Cod sursa (job #2107618)
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
ifstream in ("sortaret.in");
ofstream out ("sortaret.out");
const int MAX = 100005;
bool beenThere[MAX];
vector < int > myVector1[MAX];
vector < int > myVector2[MAX];
vector < int > newVector[MAX];
int Timp[MAX];
int Count;
int Retin;
int Answer;
int N,M;
void Read()
{
in >> N >> M;
int x,y;
while ( in >> x >> y)
{
myVector1[x].push_back(y);
myVector2[y].push_back(x);
}
}
void DFS(int Nod)
{
beenThere[Nod] = true;
for ( size_t i = 0 ; i < myVector1[Nod].size() ; ++i)
{
int Vecin = myVector1[Nod][i];
if(beenThere[Vecin] == false)
{
beenThere[Vecin] = true;
DFS(Vecin);
}
}
Timp[++Count] = Nod;
}
void DFStranspus(int Nod)
{
beenThere[Nod] = true;
newVector[Answer].push_back(Nod);
for( size_t i = 0; i < myVector2[Nod].size() ; ++i)
{
int Vecin = myVector2[Nod][i];
if(beenThere[Vecin] == false)
{
DFStranspus(Vecin);
}
}
}
void Rezolv()
{
for (int i = 1; i <= N ; ++i)
if(beenThere[i] == false)
DFS(i);
for ( int i = 1; i <= N ; ++i)
beenThere[i] = false;
for ( int i = N ; i >= 1 ; --i)
{
if(beenThere[Timp[i]] == false)
{ Answer++;
DFStranspus(Timp[i]);
}
}
int ok = true;
for ( int i = 1; i <= Answer; ++i)
if(newVector[i].size() > 1)
{
ok = false;
break;
}
if( ok == true )
for ( int i = N; i >= 1 ; --i) out << Timp[i] <<" ";
}
int main()
{
Read();
Rezolv();
return 0;
}