Cod sursa(job #2615223)

Utilizator lucidanescu28Danescu Lucian lucidanescu28 Data 13 mai 2020 21:03:39
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <stdio.h>
#include <stdlib.h>
#define inf 9999999

typedef struct listNode{
    // Nodul cu care are muchie detinatorul listei 
    int node;
    // Costul dintre detinatorul listei si node
    int cost;
    struct listNode *next;
} listNode;

typedef struct graph{
    // Numarul de noduri ale grafului
    int nodes;
    // adj_heads[i] -> lista de adiacenta a nodului i 
    listNode **adj_heads;
} graph;

void addEdge(graph *g, int v1, int v2)
{
    listNode *new;
    new = (listNode *) malloc(sizeof(listNode));
    new->node = v2;
    new->next = g->adj_heads[v1];
    g->adj_heads[v1] = new;
}

void removeEdge(graph *gl, int v1, int v2)
{
	listNode *prev, *cur;
	cur = gl->adj_heads[v1];
	
	if(cur->node == v2)
	{
		listNode *aux = cur;
		cur = cur->next;
		gl->adj_heads[v1] = cur;
		free(aux);
	}
	
	while(cur)
	{
		if(cur->node == v2) break;
		prev = cur;
		cur = cur->next;
	}
	
	if(!cur) return;

	if(cur->next == NULL)
	{
		prev->next = NULL;
		free(cur);
		return;
	}
	
	prev->next = cur->next;
	free(cur);
}

graph *createGraph(int nodes)
{
    graph *g = (graph*) malloc(sizeof(graph));

    g->nodes = nodes;
    g->adj_heads = (listNode**) calloc(nodes + 1, sizeof(listNode*));

    return g;
}

void freeList(listNode *list) {
    listNode *it = list, *prev;

    while (it != NULL) {
        prev = it;
        it = it->next;
        free(prev);
    }
}

void destroyGraph(graph *g)
{   
    for (int i = 0; i <= g->nodes; i++)
        freeList(g->adj_heads[i]);

    free(g->adj_heads);
    free(g);
}

int isAdjacent(graph *g, int source, int dest)
{
    listNode *it = g->adj_heads[source];

    while (it != NULL) {
        if (it->node == dest)
            return 1;
        
        it = it->next;
    }

    return 0;
}

int nodeIndegree(graph *g, int node)
{
    int i;
    listNode *it;
    int count = 0;

    for (i = 1; i <= g->nodes; i++)
        if (i != node)
            for (it = g->adj_heads[i]; it != NULL; it = it->next)
                if (it->node == node)
                    count++;

    return count;
}

void topologicalSort(graph *g)
{
   int S[g->nodes], L[g->nodes], sIdx = 0, lIdx = 0, u;
   
   for(int i = 1; i <= g->nodes; i++)
        S[i] = L[i] = 0;

   for(int i = 1; i <= g->nodes; i++)
        if(nodeIndegree(g, i) == 0) S[sIdx++] = i;

    int idx = 0;
    while(idx < sIdx)
    {
        u = S[idx++];
        L[lIdx++] = u;

        listNode *it = g->adj_heads[u];
        while(it)
        {
            int aux = it->node;
            
            while(isAdjacent(g, u, aux)){
            	removeEdge(g, u, aux);
            }
            
            if(nodeIndegree(g, aux) == 0) S[sIdx++] = aux;  
            it = it->next;
        }
    }

   	for(int i = 0; i < lIdx; i++)
            printf("%d ", L[i]);
}

int main(){
	FILE *fin = fopen("sortaret.in", "r");
	FILE *fout = fopen("sortare.out", "w");
	int N, M, v1, v2;

	fscanf(fin, "%d%d", &N, &M);
	graph *g = createGraph(N);

	for(int i = 1; i <= M; i++){
		fscanf(fin, "%d%d", &v1, &v2);
		addEdge(g, v1, v2);
	}

	topologicalSort(g);

	return 0;
}