Untitled

 avatar
unknown
plain_text
5 months ago
2.5 kB
13
Indexable
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define int unsigned long

typedef struct Node {
    int v;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
} LinkedList;

typedef struct Graph {
    int N;
    LinkedList* adj;
} Graph;

Graph* createGraph(int N) {
    Graph* graph = malloc(sizeof(Graph));
    graph->N = N;
    graph->adj = malloc(sizeof(LinkedList) * N);
    for (int i = 0; i < N; i++) {
        graph->adj[i].head = NULL;
    }
    return graph;
}

Node* createNode(int v) {
    Node* node = malloc(sizeof(Node));
    node->v = v;
    node->next = NULL;
    return node;
}

void addEdge(Graph* graph, int from, int to) {
    Node* toNode = createNode(to);
    toNode->next = graph->adj[from].head;
    graph->adj[from].head = toNode;
}

void topologicalSort(Graph* g) {
    Graph graph = *g;
    int inDegree[graph.N];
    memset(inDegree, 0, sizeof(inDegree));
    int finalOrder[graph.N];
    int orderIndex = 0;
    for (int i = 0; i < graph.N; i++) {
        Node* head = graph.adj[i].head;
        while (head) {
            // neighbor's indegree
            inDegree[head->v]++;
            head = head->next;
        }
    }
    int groups = 0;
    int queue[graph.N];
    int front = 0, back = 0;
    for (int i = 0; i < graph.N; i++)
    {
        if (inDegree[i] == 0) {
            queue[back++] = i;
        }
    }
    while (front < back) {
        // current level is all parallel
        groups++;
        int thisLevelN = back - front;
        for (int i = 0; i < thisLevelN; i++) {
            int curNode = queue[front++];
            finalOrder[orderIndex++] = curNode;
            Node* head = graph.adj[curNode].head;
            while (head) {
                inDegree[head->v]--;
                if (inDegree[head->v] == 0) {
                    queue[back++] = head->v;
                }
                head = head->next;
            }
        }
    }
    printf("Order: ");
    for (int i = 0; i < graph.N; i++) {
        printf("%ld ", finalOrder[i]+1);
    }
    printf("\nGroups: %ld\n", groups);
}

int main(int argc, char** argv) {
    int N, M;
    scanf("%ld %ld", &N, &M);
    Graph* graph = createGraph(N);
    while(M--) {
        int from, to;
        scanf("%ld %ld", &from, &to);
        addEdge(graph, from-1, to-1);
    }
    topologicalSort(graph);
    return 0;
}
Editor is loading...
Leave a Comment