DFS

// 9181320149_SimeonVarbanov_A
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Vertex {
    unsigned int vertex_no;
    unsigned int color; // 0: unvisited, 1: visited, 2: finished
    unsigned int time_stamp_visit;
    unsigned int time_stamp_finish;
    struct Vertex * adj_vertex;
} Vertex;

void DFS(Vertex *);
Vertex * getLastVertex(Vertex *);
Vertex * graph;
void printResult();
unsigned int edge[1000][1000];

unsigned int time_stamp = 0;
unsigned int num_of_vertices;

int main(void) {

    Vertex * last_vertex;
    Vertex * new_vertex;
    int i, x, y, tmp1;

    scanf("%d", &num_of_vertices);

    graph = (Vertex *) malloc((num_of_vertices+1) * sizeof(Vertex));
    for (i = 1; i <= num_of_vertices; i++) {
        (graph+i)->vertex_no = i;
        (graph+i)->adj_vertex = NULL;
        (graph+i)->color = 0;
        (graph+i)->time_stamp_visit = 0;
        (graph+i)->time_stamp_finish = 0;
    }

    while (1) {
        tmp1 = scanf("%d", &x);
        if (tmp1 == EOF) // fix here
            break;
        scanf("%d", &y);

        new_vertex = (Vertex *) malloc(sizeof(Vertex));
        new_vertex->adj_vertex = NULL;
        new_vertex->vertex_no = y;
        new_vertex->time_stamp_visit = 0;
        new_vertex->time_stamp_finish = 0;

        last_vertex = getLastVertex((graph+x));
        last_vertex->adj_vertex = new_vertex;
    }

    for (i = 1; i <= num_of_vertices; i++) {
        if ((graph+i)->color != 2)
            DFS((graph+i));
    }

    printResult();
    return 0;
}

void DFS(Vertex * vertex) {
    Vertex * tmp_vertex = (graph+vertex->vertex_no);

    // can only visit if it has not been visited yet
    (graph+vertex->vertex_no)->time_stamp_visit = ++time_stamp;
    (graph+vertex->vertex_no)->color = 1; // be gray, mark visited

    while (tmp_vertex->adj_vertex != NULL) {
        tmp_vertex = tmp_vertex->adj_vertex;
        if ((graph+tmp_vertex->vertex_no)->color == 0) { // if vertex is White (not visited)

            edge[vertex->vertex_no][tmp_vertex->vertex_no] = 1; // tree edge
            DFS(tmp_vertex); // visit and DFS from this vertex

        } else if ((graph+tmp_vertex->vertex_no)->color == 1) { // if vertex is Gray (visited)

            edge[vertex->vertex_no][tmp_vertex->vertex_no] = 2; // back edge

        } else if ((graph+tmp_vertex->vertex_no)->color == 2) {  // if vertex is Black (finished)

            edge[vertex->vertex_no][tmp_vertex->vertex_no] = 3; // check later
        }
    }

    (graph+vertex->vertex_no)->color = 2; //finished
    (graph+vertex->vertex_no)->time_stamp_finish = ++time_stamp;
}

Vertex * getLastVertex(Vertex * vertex) {
    Vertex *tmp = vertex;

    while (tmp->adj_vertex != NULL)
        tmp = tmp->adj_vertex;
    return tmp;
}

void printResult() {
    int i;
    Vertex *tmp;
    for (i = 1; i <= num_of_vertices; i++) {
        tmp = (graph+i);
        while (tmp->adj_vertex != NULL) {
            tmp = tmp->adj_vertex;
            if (edge[i][tmp->vertex_no] != 3)
                printf("%d %d %d\n", i, tmp->vertex_no, edge[i][tmp->vertex_no]);
            else {
                if (((graph+tmp->vertex_no)->time_stamp_visit > (graph+i)->time_stamp_visit)            // check if it is forward or cross edge by time interval
                    && ((graph+tmp->vertex_no)->time_stamp_finish < (graph+i)->time_stamp_finish))
                    printf("%d %d %d\n", i, tmp->vertex_no, 3);
                else
                    printf("%d %d %d\n", i, tmp->vertex_no, 4);
            }
        }
    }
}