Pagini recente » Cod sursa (job #657251) | Cod sursa (job #552037) | Cod sursa (job #730673) | Cod sursa (job #2113080) | Cod sursa (job #2424580)
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 50100
#define MMAX 101101
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <int> graf[NMAX];
vector <int> sortareTopologica;
int N, M, timp , tata[NMAX], culoare[NMAX], d[NMAX], final[NMAX],viz[NMAX];
void citireGraf()
{
int i, x, y;
for (i = 0; i < M; i++)
{
f >> x >> y;
graf[x].push_back(y);
}
}
void vizita(int nodCurent)
{
culoare[nodCurent] = 1;
timp++;
d[nodCurent] = timp;
int lim = graf[nodCurent].size();
for (int i = 0; i < lim; i++)
{
int vecin = graf[nodCurent][i];
if (culoare[vecin] == 0)
{
tata[vecin] = nodCurent;
vizita(vecin);
}
}
culoare[nodCurent] = 2;
sortareTopologica.insert(sortareTopologica.begin(), nodCurent);
timp++;
final[nodCurent] = timp;
}
void CA()
{
for (int i = 1; i <= N; i++)
{
culoare[i] = 0;
tata[i] = 0;
}
timp = 0;
for (int i = 1; i <= N; i++)
{
if (culoare[i] == 0)
{
vizita(i);
}
}
}
void DFS(int nod)
{
viz[nod] = 1;
int n = graf[nod].size();
for (int i = 0; i < n; i++)
{
int aux = graf[nod][i];
if (viz[aux] == 0)
DFS(aux);
}
g << nod << " ";
}
int main()
{
f >> N >> M;
citireGraf();
CA();
/*for (int i = 1; i <= N; i++)
if (viz[i] == 0)
DFS(i);*/
/*for (int i = 1; i <= N; i++)
{
cout <<i<<" "<< d[i] << " " << final[i] << endl;
}*/
for (auto &x : sortareTopologica)
g << x<<" ";
}