Algorithm-and-Data-Structure/AlgorithmCode/ArticulationPoint.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
109
110
111
112
113
importjava.util.ArrayList;

publicclassArticulationPoint {
intids[];
intlows[];
intid;
booleanvisited[];
booleanisArt[];
intOutGoingEdge;

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

// 컷 에지 dfs 시작
publicvoiddfs (Graphgraph, intcur, intparent, introot) {
if (parent == root)
OutGoingEdge++;
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, root);
lows[cur] = min(lows[cur], lows[to]);
if (ids[cur] < lows[to]) {
isArt[cur] = true;
 }
if (ids[cur] == lows[cur]) {
isArt[cur] = true;
 }
 }else {
lows[cur] = min(ids[to], lows[cur]);
 }
 }
 }

// 컷 에지 메소드, dfs 헬퍼 메소드
voiddoArticulationPointAlgorithm(Graphgraph, intn) {

ids = newint[n];
lows = newint[n];
visited = newboolean[n];
isArt = newboolean[n];

// Seek Cut Edge
intstart = 0;
dfs(graph, start, -1, -1);
// 시작 점은 진출 차수가 0 또는 1이면 단절점이 될 수 없다.
// 0 : 노드 1개, 자기 자신, 1: 사이클인 경우 갇힘, 사이클이 아니라면 단절점이 아니다.
if (OutGoingEdge < 2)
isArt[start] = false;
 }

// For construct graph - 그래프 클래스
staticclassGraph {
ArrayList<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 ==> Articulation point will be 2, 3, 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);

ArticulationPointart = newArticulationPoint();
art.doArticulationPointAlgorithm(graph, n);

// Output : 2 3 5
for (inti = 0; i < art.isArt.length; i++) {
if (art.isArt[i])
System.out.print(i + " ");
 }
 }
}