Algorithm-and-Data-Structure/AlgorithmCode/CutEdge.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
importjava.util.ArrayList;

publicclassCutEdge {
privateintids[];
privateintlows[];
privateintid;
privatebooleanvisited[];
privateArrayList<Edge> cutEdgeList;

publicintmin (inta, intb) {
returna < b ? a : b;
 }

staticclassEdge {
privateintfrom;
privateintto;

publicEdge(intfrom, intto) {
this.from = from;
this.to = to;
 }
 }

publicvoiddfs (Graphgraph, intcur, intparent) {
visited[cur] = true;
ids[cur] = id;
lows[cur] = id;
id++;

for (intto : graph.graph[cur]) {
if (parent == to)
continue;
if (!visited[to]) {
dfs(graph, to, cur);
lows[cur] = min(lows[cur], lows[to]);
if (ids[cur] < lows[to])
cutEdgeList.add(newEdge(cur, to));
 }else {
lows[cur] = min(ids[to], lows[cur]);
 }
 }
 }

publicvoiddoCutEdgeAlgorithm(Graphgraph, intn) {
ids = newint[n];
lows = newint[n];
visited = newboolean[n];
cutEdgeList = newArrayList<>();

// Seek Cut Edge
dfs(graph, 0, -1);

// Print Cut Edge
// Output will be : 3-4 2-3 2-5
for (EdgecutEdge : cutEdgeList) {
System.out.print(cutEdge.from + "-" + cutEdge.to + " ");
 }
 }

// For construct graph
staticclassGraph {
privateArrayList<Integer> graph[];

publicGraph(intn) {
graph = newArrayList[n];
for (inti = 0; i < n; i++) {
graph[i] = newArrayList<>();
 }
 }

publicvoidaddEdge(inta, intb) {
graph[a].add(b);
graph[b].add(a);
 }
 }

/*

 Sample Graph

 0 6
 / \ / \
 1 - 2 - 5 7 ==> Cut Edge will be 3-4, 2-3, 2-5
 | \ /
 3 8
 \
 4

 */

publicstaticvoidmain(String[] args) {
intn = 9;
Graphgraph = newGraph(n);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(5, 6);
graph.addEdge(5, 8);
graph.addEdge(6, 7);
graph.addEdge(7, 8);

CutEdgecutEdge = newCutEdge();
cutEdge.doCutEdgeAlgorithm(graph, n);
 }
}