My issue
write full code for question
Topological sort
My code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXV 10000
typedef struct Node {
int vertex;
struct Node* next;
} Node;
Node* adj[MAXV];
int inDegree[MAXV];
int topoSort[MAXV];
int pq[MAXV];
int pqSize;
Node* createNode(int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
void addEdge(int u, int v) {
Node* newNode = createNode(v);
newNode->next = adj[u];
adj[u] = newNode;
inDegree[v]++;
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void push(int value) {
pq[pqSize++] = value;
int child = pqSize - 1;
int parent = (child - 1) / 2;
while (child > 0 && pq[child] < pq[parent]) {
swap(&pq[child], &pq[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
int pop() {
int minValue = pq[0];
pq[0] = pq[--pqSize];
int parent = 0;
while (1) {
int left = 2 * parent + 1;
int right = 2 * parent + 2;
int minIndex = parent;
if (left < pqSize && pq[left] < pq[minIndex]) {
minIndex = left;
}
if (right < pqSize && pq[right] < pq[minIndex]) {
minIndex = right;
}
if (minIndex == parent) {
break;
}
swap(&pq[parent], &pq[minIndex]);
parent = minIndex;
}
return minValue;
}
void topologicalSort(int n) {
pqSize = 0;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
push(i);
}
}
int index = 0;
while (pqSize > 0) {
int u = pop();
topoSort[index++] = u;
Node* current = adj[u];
while (current != NULL) {
int v = current->vertex;
inDegree[v]--;
if (inDegree[v] == 0) {
push(v);
}
current = current->next;
}
}
// Print the topological sort
for (int i = 0; i < index; i++) {
printf("%d ", topoSort[i]);
}
printf("\n");
}
void freeGraph(int n) {
for (int i = 0; i < n; i++) {
Node* current = adj[i];
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int N, M;
scanf("%d %d", &N, &M);
// Initialize the graph
for (int i = 0; i < N; i++) {
adj[i] = NULL;
inDegree[i] = 0;
}
// Read the edges
for (int i = 0; i < M; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
// Perform topological sort
topologicalSort(N);
// Free the graph
freeGraph(N);
}
return 0;
}
Learning course: Analysis and Design of Algorithms
Problem Link: Topological sort in Analysis and Design of Algorithms