Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <stdlib.h>
- enum Colour {
- WHITE, //0 ни разу НЕ ЗАХОДИЛИ
- GREY, //1 ЗАШЛИ , но обрабатываем следущие
- BLACK, //2 НИКУДА не ведет
- };
- typedef struct listNode {
- int from;
- int to;
- struct listNode * Next;
- } list;
- void matrix_create(list *mas, int rib_count , int top_count) // создание нового узла
- {
- int Start; //начало и конец ребра (S)-->(F)
- int Finish;
- for (int i = 0; i < rib_count; i++)
- {
- if (scanf("%d %d", &Start, &Finish) != 2) {
- printf("bad number of lines\n");
- exit(0);
- }
- if ((Start <= 0) || (Start > top_count) || (Finish <= 0) || (Finish > top_count)) {
- printf("bad vertex\n");
- exit(0);
- }
- mas[i].from = Start;
- mas[i].to = Finish;
- }
- }
- void dfs(list *mas, char *WGB, int i, short int *out_put, int* p ,int rib_count)
- {
- int j;
- if (WGB[i - 1] == BLACK) {
- return;
- }
- //list *tmp = *List;
- WGB[i - 1] = GREY;
- for (int z = 0; z< rib_count; z++)
- {
- if ((mas[j].from) == i)
- {
- if (WGB[(mas[j].to) - 1] == GREY)
- {
- printf("impossible to sort");
- exit(0);
- }
- if (WGB[(mas[j].to) - 1] == WHITE)
- {
- int l = mas[j].to;
- dfs(mas, WGB, l, out_put, p,mas,rib_count );//здесь вместо tmp->to нужно использовать рассматриваемае значение ранее
- }
- }
- j++;
- }
- WGB[i - 1] = BLACK;
- out_put[(*p)++] = i;
- int k = *p - 1;
- }
- int proverka(int top_count, int rib_count)
- {
- if (top_count > 1000 || top_count < 0)
- {
- printf("bad number of vertices");
- return 0;
- }
- if (rib_count > top_count*(top_count + 1) / 2 || rib_count < 0)
- {
- printf("bad number of edges");
- return 0;
- }
- return 0;
- }
- int main() {
- list *head = malloc(sizeof(list));
- int i, p = 0;
- int rib_count;
- int top_count;
- if (scanf("%d %d", &top_count, &rib_count) != 2) {
- printf("bad number of lines\n");
- return 0;
- }
- int *mas1 = (int*)malloc(sizeof(int));
- list *mas = malloc(sizeof(list));
- proverka(top_count, rib_count);
- short int *out_put = malloc(top_count * sizeof(int));
- char *WGB = (char*)calloc(top_count, sizeof(char));
- matrix_create(head, rib_count, top_count);
- for (i = 1; i <= top_count; i++) {
- dfs(mas, WGB, i, out_put, &p,rib_count);
- }
- for (i = 0; i < top_count; i++)
- {
- printf("%d\n", out_put[top_count - 1 - i]);
- }
- free(out_put);
- free(WGB);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement