8000 Merge pull request #690 from ajjuthekaal/patch-2 · glitches-coder/Algorithms@ed51828 · GitHub
[go: up one dir, main page]
Skip to content

Commit ed51828

Browse files
i-vishii-vishi
authored
Merge pull request VAR-solutions#690 from ajjuthekaal/patch-2
Create Kosaraju_ALgorithm.cpp
2 parents e0843ae + 6a4a538 commit ed51828

File tree

1 file changed

+91
-0
lines changed

1 file changed

+91
-0
lines changed

‎Graphs/Kosaraju ALgorithm/Kosaraju_ALgorithm.cpp

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
4+
#define MAX_DEGREE 5
5+
#define MAX_NUM_VERTICES 20
6+
7+
struct vertices_s {
8+
int visited;
9+
int deg;
10+
int adj[MAX_DEGREE]; /* < 0 if incoming edge */
11+
} vertices[] = {
12+
{0, 3, {2, -3, 4}},
13+
{0, 2, {-1, 3}},
14+
{0, 3, {1, -2, 7}},
15+
{0, 3, {-1, -5, 6}},
16+
{0, 2, {4, -7}},
17+
{0, 3, {-4, 7, -8}},
18+
{0, 4, {-3, 5, -6, -12}},
19+
{0, 3, {6, -9, 11}},
20+
{0, 2, {8, -10}},
21+
{0, 3, {9, -11, -12}},
22+
{0, 3, {-8, 10, 12}},
23+
{0, 3, {7, 10, -11}}
24+
};
25+
int num_vertices = sizeof(vertices) / sizeof(vertices[0]);
26+
27+
struct stack_s {
28+
int top;
29+
int items[MAX_NUM_VERTICES];
30+
} stack = {-1, {}};
31+
32+
void stack_push(int v) {
33+
stack.top++;
34+
if (stack.top < MAX_NUM_VERTICES)
35+
stack.items[stack.top] = v;
36+
else {
37+
printf("Stack is full!\n");
38+
exit(1);
39+
}
40+
}
41+
42+
int stack_pop() {
43+
return stack.top < 0 ? -1 : stack.items[stack.top--];
44+
}
45+
46+
void dfs(int v, int transpose) {
47+
int i, c, n;
48+
vertices[v].visited = 1;
49+
for (i = 0, c = vertices[v].deg; i < c; ++i) {
50+
n = vertices[v].adj[i] * transpose;
51+
if (n > 0)
52+
/* n - 1 because vertex indexing begins at 0 */
53+
if (!vertices[n - 1].visited)
54+
dfs(n - 1, transpose);
55+
}
56+
if (transpose < 0)
57+
stack_push(v);
58+
else
59+
printf("%d ", v + 1);
60+
}
61+
62+
void reset_visited() {
63+
int i;
64+
for (i = 0; i < num_vertices; ++i)
65+
vertices[i].visited = 0;
66+
}
67+
68+
void order_pass() {
69+
int i;
70+
for (i = 0; i < num_vertices; ++i)
71+
if (!vertices[i].visited)
72+
dfs(i, -1);
73+
}
74+
75+
void scc_pass() {
76+
int i = 0, v;
77+
while((v = stack_pop()) != -1) {
78+
if (!vertices[v].visited) {
79+
printf("scc %d: ", ++i);
80+
dfs(v, 1);
81+
printf("\n");
82+
}
83+
}
84+
}
85+
86+
int main(void) {
87+
order_pass();
88+
reset_visited();
89+
scc_pass();
90+
return 0;
91+
}

0 commit comments

Comments
 (0)
0