acyclic test

//
//  main.c
//  acyclic test
//
//  Created by Александр on 08.05.2557 BE.
//  Copyright (c) 2557 Alexander Guschin. All rights reserved.
//


#include <stdio.h>
#include <stdlib.h>
int *visited;
int *ccarray;
int *timeb, *timee; // время начало, время конца
int cycle = 0;
int ccnum = 0;
int count = 0;

struct vertex {
    int key; // вершина графа
    struct vertex *next;
};


void printGraph(struct vertex *graph, int n)
{
    struct vertex *pntVertex;
    for (int i = 1; i < n; i++) {
        printf("%d:", graph[i].key);
        pntVertex = graph[i].next;
        while (pntVertex != NULL) {
            printf(" %d", pntVertex->key);
            pntVertex = pntVertex->next;
        }
        printf("\n");
    }
}


void initGraph(int n, struct vertex *graph)
{
    for (int i = 1; i < n; i++) {
        graph[i].key = i;
    }
}


void addEdge(int x, int y, struct vertex *graph)
{
    struct vertex *newVertex;
    newVertex = (struct vertex*)malloc(sizeof(struct vertex));
    newVertex->key = y;
    newVertex->next = graph[x].next;
    graph[x].next = newVertex;
}


void explore(struct vertex *graph, struct vertex *pnt, int n)
{
    int temp = pnt->key;
    visited[temp] = 1;
    ccarray[temp] = ccnum;
    count++;
    timeb[temp] = count;
    pnt = pnt->next;
    while (pnt != NULL) {
        if (!visited[pnt->key]) {
            explore(graph, &graph[pnt->key], n);
        }
        else if (timeb[pnt->key] && !timee[pnt->key]) // если есть время начало след.вершины и нет времени ее окончания - цикл
            cycle = 1;
        pnt = pnt->next;
    }
    timee[temp] = count;
    
    
}



void dfs(struct vertex *graph, int n)
{
    ccarray = (int*)calloc(n, sizeof(int));
    for (int i = 1; i < n; i++) {
        if (!visited[graph[i].key]) {
            explore(graph, &graph[i], n);
            ccnum++;
        }
    }
}


int main(int argc, const char * argv[])
{
    int n, m, x, y;
    struct vertex *graph;
    scanf("%d", &n); // вершины
    scanf("%d", &m); // ребра
    n++;
    graph = (struct vertex*)calloc(n, sizeof(struct vertex));
    timeb = (int*)calloc(n, sizeof(int));
    timee = (int*)calloc(n, sizeof(int));
    initGraph(n, graph);
    
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        scanf("%d", &y);
        addEdge(x, y, graph);
        //        addEdge(y, x, graph);
    }
    
    visited = (int *)calloc(n, sizeof(int));
    dfs(graph, n);
    
    if (cycle) {
        printf("True\n");
    }
    else
        printf("False\n");
    
    return 0;
}