Pagini recente » Cod sursa (job #2613666) | Cod sursa (job #2597065) | Cod sursa (job #65265) | Cod sursa (job #1616107) | Cod sursa (job #2615223)
#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;
}