Cod sursa(job #2619009)

Utilizator RaduQQTCucuta Radu RaduQQT Data 26 mai 2020 18:32:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#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;
		}
	}
	

}