Cod sursa(job #613240)

Utilizator jokkerbogdan ghit jokker Data 19 septembrie 2011 16:16:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#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;
}