Pagini recente » Cod sursa (job #2835535) | Cod sursa (job #1049209) | Cod sursa (job #343039) | Cod sursa (job #2665502) | Cod sursa (job #2619009)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct listNode
{
listNode* next;
int element;
};
void pushQueue(listNode*& head, listNode*& tail, int element)
{
listNode* node = (listNode*)malloc(sizeof(listNode));
node->element = element;
if (head ==NULL)
{
head = node;
tail = node;
head->next = tail;
return;
}
tail->next = node;
tail = tail->next;
tail->next = NULL;
}
void popQueue(listNode*& head, listNode*& tail)
{
if (head == tail)
{
free(head);
head = NULL;
return;
}
listNode* node = head;
head = head->next;
free(node);
}
void insertNodeInList(listNode*& head, int element)
{
listNode* node = (listNode*)malloc(sizeof(listNode));
node->element = element;
if (head == NULL)
{
head = node;
head->next = NULL;
return;
}
node->next = head;
head = node;
}
listNode *head[50001];
bool visited[50001];
int grad[50001];
int main()
{
int n,m;
FILE* fin = fopen("sortaret.in", "r");
FILE* fout = fopen("sortaret.out", "w");
fscanf(fin, "%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
head[i] = NULL;
}
int a, b;
listNode* head1 = NULL,*tail1 = NULL;
for (int i = 0; i < m; i++)
{
fscanf(fin, "%d%d", &a, &b);
int ok = 1;
listNode* p = head[a];
while (p != NULL)
{
if (p->element == b)
{
ok = 0;
break;
}
p = p->next;
}
if (ok)
{
insertNodeInList(head[a], b);
grad[b]++;
}
}
for (int i = 1; i <= n; i++)
if (!grad[i])
pushQueue(head1, tail1, i);
while (head1 != NULL)
{
int el = head1->element;
visited[el] = 1;
popQueue(head1, tail1);
fprintf(fout,"%d ", el);
while (head[el] != NULL)
{
grad[head[el]->element]--;
if (!grad[head[el]->element] && !visited[head[el]->element])
pushQueue(head1, tail1, head[el]->element);
head[el] = head[el]->next;
}
}
}