Pagini recente » Cod sursa (job #316340) | Cod sursa (job #815751) | Cod sursa (job #450994) | Cod sursa (job #625895) | Cod sursa (job #613240)
Cod sursa(job #613240)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define WHITE 0
#define GREY 1
#define BLACK 2
#define MAXN 50000
using namespace std;
int N, M;
typedef vector<int> vector_int;
vector_int A[MAXN];
vector_int order;
int start[MAXN], stop[MAXN], color[MAXN];
int time;
void readGraph()
{
int i, j, k;
scanf("%d %d", &N, &M);
for (k = 0; k < M; k++) {
scanf("%d %d", &i, &j);
i--; j--;
A[i].push_back(j);
}
}
void printGraph()
{
int i, j;
vector_int::iterator it;
for (i = 0; i < N; i++) {
printf("%d: ", i);
for (it = A[i].begin(); it != A[i].end(); it++) {
printf("%d ", *it);
}
printf("\n");
}
}
void DFS(int n)
{
int j;
vector_int::iterator it;
color[n] = GREY;
start[n] = time;
time++;
for (it = A[n].begin(); it != A[n].end(); it++) {
if (color[*it] == GREY) {
//printf("Error cycle");
exit(1);
}
if (color[*it] == WHITE)
DFS(*it);
}
color[n] = BLACK;
stop[n] = time;
order.push_back(n+1);
time++;
}
int main(int argc, char** args)
{
int i;
vector_int::reverse_iterator it;
freopen("sortaret.in", "rt", stdin);
freopen("sortaret.out", "wt", stdout);
readGraph();
for (i = 0; i < N; i++)
if (color[i] == WHITE)
DFS(i);
for (it = order.rbegin(); it != order.rend(); it++)
printf("%d ", *it);
printf("\n");
return 0;
}