#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

struct Node
{
    int value;
    struct Node* next;
};

struct Graph
{
    int numNodes;
    struct Node* adjacencyList[MAX_NODES];
};

// initializare graf
void initializeGraph(struct Graph* graph, int numNodes)
{
    graph->numNodes = numNodes;
    for (int i = 0; i < numNodes; ++i)
        graph->adjacencyList[i] = NULL;
}

// adăugare muchie
void addEdge(struct Graph* graph, int src, int dest)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = dest;
    newNode->next = graph->adjacencyList[src];
    graph->adjacencyList[src] = newNode;
}

// funcție auxiliară pentru sortarea topologică recursivă
void topologicalSortUtil(struct Graph* graph, int node, int visited[], int stack[], int* stackIndex)
{
    visited[node] = 1;

    // parcurgem vecinii nodului curent și aplicam sortarea topologică pentru ei
    struct Node* current = graph->adjacencyList[node];
    while (current != NULL)
    {
        int neighbor = current->value;
        if (!visited[neighbor])
            topologicalSortUtil(graph, neighbor, visited, stack, stackIndex);
        current = current->next;
    }

    // după ce am parcurs toți vecinii, adăugam nodul curent în stack
    stack[(*stackIndex)++] = node;
}

// sortare topologică
void topologicalSort(struct Graph* graph)
{
    int visited[MAX_NODES] = {0};
    int stack[MAX_NODES];
    int stackIndex = 0;

    // parcurgem toate nodurile și aplicam sortarea topologică pentru fiecare nod nevizitat
    for (int i = 0; i < graph->numNodes; ++i)
        if (!visited[i])
            topologicalSortUtil(graph, i, visited, stack, &stackIndex);

    // afisam rezultatul sortării topologice (în ordinea inversă a stack-ului)
    printf("sortarea topologica a grafului:\n");
    while (stackIndex > 0)
        printf("%d ", stack[--stackIndex]);
    printf("\n");
}

int main()
{
    struct Graph graph;
    int numNodes, numEdges, src, dest;

    printf("introdu numarul de noduri si numarul de muchii ale grafului: ");
    scanf("%d %d", &numNodes, &numEdges);

    initializeGraph(&graph, numNodes);

    printf("introdu muchiile (perechile de noduri):\n");
    for (int i = 0; i < numEdges; ++i)
    {
        scanf("%d %d", &src, &dest);
        addEdge(&graph, src, dest);
    }

    topologicalSort(&graph);

    return 0;
}