lab7

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

enum InitializeState {
    OK, BAD_NUMBER_OF_VERTICES, BAD_NUMBER_OF_EDGES, BAD_VERTEX, BAD_NUMBER_OF_LINES_BEFORE, BAD_NUMBER_OF_LINES_AFTER
};

enum SortState {
    SORTED, IMPOSSIBLE_TO_SORT
};

enum Colors {
    WHITE = 1,
    GREY = 2,
    BLACK = 3
};

enum InitializeState checkVertex(const int vertex, const int N) {
    if (vertex <= 0 || vertex > N)
        return BAD_VERTEX;
    return OK;
}

int getBytePosition(const int vertex) {
    return (vertex - 1) / 8 + 1;
}

int getVertexInBitRepresentation(const int vertex) {
    return 1 << (7 - (vertex % 8));
}

void addVertexToMatrix(char **matrix, const int from_vertex, const int to_vertex) {
    if (matrix == NULL)
        return;
    matrix[from_vertex - 1][getBytePosition(to_vertex)] |= getVertexInBitRepresentation(to_vertex);
}

int isVertexInMatrix(char **matrix, const int from_vertex, const int to_vertex) {
    return matrix[from_vertex - 1][getBytePosition(to_vertex)] & getVertexInBitRepresentation(to_vertex);
}

char **createMatrix(const int N) {
    char **arr = (char **) calloc(N, sizeof(char *));
    for (int i = 0; i < N; ++i) {
        arr[i] = calloc(getBytePosition(N) + 1, sizeof(char));
        arr[i][0] = WHITE;
    }
    return arr;
}

void initializeMatrix(char **matrix, const int from_vertex, const int to_vertex) {
    addVertexToMatrix(matrix, from_vertex, to_vertex);
}

int dfs(char **matrix, const int N, const int vertex, int *res) {
    if (matrix[vertex - 1][0] == WHITE) {
        static int c = 0;
        matrix[vertex - 1][0] = GREY;
        for (int j = N; j >= 1; --j) {
            if (isVertexInMatrix(matrix, vertex, j))
                if (dfs(matrix, N, j, res) == IMPOSSIBLE_TO_SORT)
                    return IMPOSSIBLE_TO_SORT;
        }
        matrix[vertex - 1][0] = BLACK;
        res[c++] = vertex;
    }
    if (matrix[vertex - 1][0] == GREY)
        return IMPOSSIBLE_TO_SORT;
    return SORTED;
}

int topologicalSort(char **matrix, const int N, int *res) {
    for (int i = 0; i < N; ++i) {
        if (matrix[i][0] == WHITE) {
            if (dfs(matrix, N, i + 1, res) == IMPOSSIBLE_TO_SORT) {
                return IMPOSSIBLE_TO_SORT;
            }
        }
        if (matrix[i][0] == GREY) {
            return IMPOSSIBLE_TO_SORT;
        }
    }
    return SORTED;
}

void freeMem(char **arr, const int N) {
    for (int i = 0; i < N; ++i) {
        free(arr[i]);
    }
    free(arr);
}

void printResult(const int *res, const int N) {
    for (int i = N - 1; i >= 0; --i) {
        if (res[i])
            printf("%d ", res[i]);
    }
}

enum InitializeState initializeVariables(int *N, int *M, char ***array) {
    int lines = 0;
    int read = 0;
    if ((read = fscanf(stdin, "%d", N)) != EOF && read > 0) {
        if (*N > 2000 || *N < 0) {
            return BAD_NUMBER_OF_VERTICES;
        }
        lines++;
    } else {
        return BAD_NUMBER_OF_LINES_BEFORE;
    }
    if ((read = fscanf(stdin, "%d", M)) != EOF && read > 0) {
        if (*M < 0 || *M > (*N * (*N + 1)) / 2) {
            return BAD_NUMBER_OF_EDGES;
        }
        lines++;
    } else {
        return BAD_NUMBER_OF_LINES_BEFORE;
    }
    int from_vertex, to_vertex;
    *array = createMatrix(*N);
    while ((read = fscanf(stdin, "%d %d", &from_vertex, &to_vertex)) != EOF && read > 0) {
        lines++;
        if (checkVertex(from_vertex, *N) == BAD_VERTEX || checkVertex(to_vertex, *N) == BAD_VERTEX) {
            return BAD_VERTEX;
        }
        initializeMatrix(*array, from_vertex, to_vertex);
    }

    if (lines < *M + 2) {
        return BAD_NUMBER_OF_LINES_AFTER;
    }
    return OK;
}

int main(void) {
    int N;
    int M;
    char **map = NULL;
    int res[2001] = {0};
    switch (initializeVariables(&N, &M, &map)) {
        case BAD_VERTEX:
            freeMem(map, N);
            puts("bad vertex");
            return 0;
        case BAD_NUMBER_OF_LINES_BEFORE:
            puts("bad number of lines");
            return 0;
        case BAD_NUMBER_OF_LINES_AFTER:
            freeMem(map, N);
            puts("bad number of lines");
            return 0;
        case BAD_NUMBER_OF_EDGES:
            puts("bad number of edges");
            return 0;
        case BAD_NUMBER_OF_VERTICES:
            puts("bad number of vertices");
            return 0;
        case OK:
            break;
    }
    if (topologicalSort(map, N, res) == IMPOSSIBLE_TO_SORT) {
        puts("impossible to sort");
        freeMem(map, N);
        return 0;
    }
    freeMem(map, N);
    printResult(res, N);

    return EXIT_SUCCESS;
}