Untitled
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