Social network connectivity
package unionFind
;
import java
.io
.*
;
import java
.util
.*
;
import edu
.princeton
.cs
.algs4
.StdOut
;
public class SocialNetworkUF {
private QuickUnionUF uf
;
public SocialNetworkUF(int num
) {
uf
= new QuickUnionUF(num
);
}
public String
getEarliestConTime(FileInputStream ins
) {
try {
Scanner scanner
= new Scanner(ins
,"utf-8");
String earliestConTime
= null
;
while(scanner
.hasNextLine()) {
String line
= scanner
.nextLine();
if(line
!= null
&& !line
.trim().equals("")) {
String
[] lineArray
= line
.split(" ");
if(lineArray
.length
== 3) {
String timestamp
= lineArray
[0];
int p
= Integer
.parseInt(lineArray
[1]);
int q
= Integer
.parseInt(lineArray
[2]);
if(!uf
.connected(p
, q
)) {
uf
.union(p
, q
);
}
if(uf
.count() == 1) {
earliestConTime
= timestamp
;
return earliestConTime
;
}
}
}
}
} catch (Exception e
) {
e
.printStackTrace();
}
return "不存在这样的时间";
}
public static void main(String
[] args
) {
try {
FileInputStream ins
= new FileInputStream("socialNetworkLog.txt");
SocialNetworkUF socialNet
= new SocialNetworkUF(10);
String earliestConTime
= socialNet
.getEarliestConTime(ins
);
StdOut
.println("the earliest connectet time is :" + earliestConTime
);
} catch (FileNotFoundException e
) {
e
.printStackTrace();
}
}
}
Union-find with specific canonical element.
package unionFind
;
import edu
.princeton
.cs
.algs4
.StdOut
;
public class UFWithFindLargest {
private int[] id
;
private int[] sz
;
private int[] large
;
public UFWithFindLargest(int N
){
sz
= new int[N
];
id
= new int[N
];
large
= new int[N
];
for(int i
= 0; i
< id
.length
; i
++) {
id
[i
] = i
;
sz
[i
] = 1;
large
[i
] = i
;
}
}
private int root(int i
) {
while(id
[i
] != i
) {
id
[i
] = id
[id
[i
]];
i
= id
[i
];
}
return i
;
}
public int findLargest(int i
) {
return large
[root(i
)];
}
public boolean connected(int p
, int q
) {
return (root(p
) == root(q
));
}
public void union(int p
,int q
) {
int proot
= root(p
);
int qroot
= root(q
);
if(proot
== qroot
) {
return;
}
if(sz
[proot
] < sz
[qroot
]) {
id
[proot
] = qroot
;
sz
[qroot
] += sz
[proot
];
if(large
[proot
] > large
[qroot
]) {
large
[qroot
] = large
[proot
];
}
}else {
id
[qroot
] = proot
;
sz
[proot
] += sz
[qroot
];
if(large
[qroot
] > large
[proot
]) {
large
[proot
] = large
[qroot
];
}
}
}
public static void main(String
[] args
) {
UFWithFindLargest uf
= new UFWithFindLargest(10);
uf
.union(0, 2);
uf
.union(2, 7);
StdOut
.println(uf
.findLargest(0) == 7);
}
}
Successor with delete
package unionFind
;
import edu
.princeton
.cs
.algs4
.StdOut
;
public class SuccessorWithDelete {
private boolean data
[];
private UFWithFindLargest uf
;
private int N
;
public SuccessorWithDelete(int N
) {
this.N
= N
;
data
= new boolean[N
];
for(int i
= 0; i
< N
; i
++) {
data
[i
] = true;
}
uf
= new UFWithFindLargest(N
);
}
public void remove(int x
) {
data
[x
] = false;
if(x
> 0 && !data
[x
-1]) {
uf
.union(x
, x
- 1);
}
if(x
< N
- 1 && !data
[x
+1]) {
uf
.union(x
, x
+1);
}
}
public int successor(int x
) {
if(data
[x
])
return x
;
else{
int res
= uf
.findLargest(x
) + 1;
if(res
>= N
) {
StdOut
.print("不存在这样的数");
return -1;
}else {
return res
;
}
}
}
public static void main(String
[] args
) {
SuccessorWithDelete test
= new SuccessorWithDelete(10);
test
.remove(2);
StdOut
.println(test
.successor(2) == 3);
StdOut
.println(test
.successor(3) == 3);
}
}
转载请注明原文地址: https://www.6miu.com/read-5033332.html
