Pagini recente » Cod sursa (job #1866053) | Cod sursa (job #3140639) | Cod sursa (job #1596850) | Cod sursa (job #850066) | Cod sursa (job #1096687)
/* Sortare topologica a varfurilor unui graf */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 50001
vector<int> Edge[MAX], Path, BigPath;
bool Was[MAX];
int N, M;
void DFS(int X)
{
Was[X] = 1;
for (int i = 0; i < Edge[X].size(); i++)
if (!Was[Edge[X][i]])
{
DFS(Edge[X][i]);
}
Path.push_back(X);
}
int main()
{
int A, B;
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d %d", &N, &M);
for (int i = 0; i < M; i++)
{
scanf("%d %d", &A, &B);
Edge[A].push_back(B);
}
for (int i = 1; i <= N; i++)
if (!Was[i])
{
Path.resize(0);
DFS(i);
reverse(Path.begin(), Path.end());
BigPath.insert(BigPath.end(), Path.begin(), Path.end());
}
for (int i = BigPath.size() - 1; i >= 0; i--)
printf("%d ", BigPath[i]);
}