-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFinderCycle.java
More file actions
111 lines (85 loc) · 2 KB
/
FinderCycle.java
File metadata and controls
111 lines (85 loc) · 2 KB
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
import java.util.*;
public class FinderCycle{
public static class Node{
public Integer Integeralue;
public Node(Integer Integer){
Integeralue= Integer;
}
}
private HashMap<Node,Node> parents;
private HashMap<Integer,Node> nodes;
private HashMap<Node,Integer> sizeMap;
public FinderCycle(List<Integer> arr){
parents = new HashMap<Node,Node>();
nodes = new HashMap<Integer,Node>();
sizeMap = new HashMap<Node,Integer>();
for (Integer cur : arr ) {
Node n = new Node(cur);
nodes.put(cur,n);
parents.put(n,n);
sizeMap.put(n,1);
}
}
public FinderCycle(List<Integer> arr,int row){
parents = new HashMap<Node,Node>();
nodes = new HashMap<Integer,Node>();
sizeMap = new HashMap<Node,Integer>();
for (int i=0; i<row; i++) {
Node n = new Node(i);
nodes.put(i,n);
parents.put(n,n);
sizeMap.put(n,1);
}
for (int i=0; i<arr.size(); i++) {
int curRow = i/row;
int curClo = i%row;
if(arr.get(i) == 1){
Union(curRow,curClo);
}
}
}
private Node Find(Integer node){
Stack<Node> stack = new Stack<Node>();
Node cur = nodes.get(node);
while(cur != parents.get(cur)){
stack.push(cur);
cur = parents.get(cur);
}
while(!stack.isEmpty()){
parents.put(stack.pop(),cur);
}
return cur;
}
public void Union(Integer a,Integer b){
Node fa = Find(a);
Node fb = Find(b);
if(fa != fb){
int sa = sizeMap.get(fa);
int sb = sizeMap.get(fb);
Node big = sa>=sb ? fa : fb;
Node small = big==fa ? fb : fa;
parents.put(small,big);
sizeMap.remove(small);
}
}
public int size(){
return sizeMap.size();
}
public static void main(String[] args){
int[][] matrix={
{1,1,0,0,0},
{1,1,1,0,0},
{0,1,1,0,0},
{0,0,0,1,0},
{0,0,0,0,1}
};
ArrayList<Integer> arr = new ArrayList<Integer>();
for (int i=0; i<matrix.length; i++) {
for (int j=0;j<matrix[i].length ;j++ ) {
arr.add(matrix[i][j]);
}
}
FinderCycle unionFind = new FinderCycle(arr,5);
System.out.println("size ="+ unionFind.size());
}
}