-
Notifications
You must be signed in to change notification settings - Fork 4
/
kosaraju.c
80 lines (67 loc) 路 1.89 KB
/
kosaraju.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "kosaraju.h"
#include "../../topological-sort/dfs/topological-sort.h"
#include "stdio.h"
#include "stdlib.h"
graph *TransposeGraph(graph *g) {
int u, v;
linked_list_node *v_node;
graph *g_t = malloc(sizeof(graph));
g_t->V = g->V;
g_t->E = g->E;
g_t->Adj = (linked_list **)malloc(sizeof(linked_list *) * (g->V));
for (u = 0; u < g->V; u++)
g_t->Adj[u] = AllocateLinkedList();
for (u = 0; u < g->V; u++) {
v_node = g->Adj[u]->nil->next;
while (v_node != g->Adj[u]->nil) {
v = v_node->key;
ListInsert(g_t->Adj[v], u);
v_node = v_node->next;
}
}
return g_t;
}
void SccDfs(graph *g, linked_list *scc, int *scc_label, int scc_index, int *c,
int u) {
int v;
linked_list_node *v_node;
c[u] = gray;
v_node = g->Adj[u]->nil->next;
while (v_node != g->Adj[u]->nil) {
v = v_node->key;
if (c[v] == white)
SccDfs(g, scc, scc_label, scc_index, c, v);
v_node = v_node->next;
}
scc_label[u] = scc_index;
ListInsert(scc, u);
}
kosaraju_result Kosaraju(graph *g) {
kosaraju_result result;
int u;
int *c = (int *)malloc(sizeof(int) * (g->V));
int *scc_label = (int *)malloc(sizeof(int) * (g->V));
linked_list **sccs = (linked_list **)malloc(sizeof(linked_list) * (g->V));
int sccs_count = 0;
int scc_index = -1;
for (u = 0; u < g->V; u++)
c[u] = white, scc_label[u] = -1;
graph *g_t = TransposeGraph(g);
linked_list *ordering = TopSort(g);
linked_list_node *ordering_node = ordering->nil->next;
while (ordering_node != ordering->nil) {
u = ordering_node->key;
if (c[u] == white) {
sccs_count++;
scc_index++;
linked_list *scc = AllocateLinkedList();
SccDfs(g_t, scc, scc_label, scc_index, c, u);
sccs[scc_index] = scc;
}
ordering_node = ordering_node->next;
}
result.scc = scc_label;
result.sccs = sccs;
result.sccs_count = sccs_count;
return result;
}