import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Digraph {
private Map<Integer, Set<Integer>> neighbors = new HashMap<>();
private Map<Integer, Integer> unionFind = new HashMap<>();
private Map<Integer, Integer> uFSize = new HashMap<>();
private Set<Integer> marked = new HashSet<>();
private int count;
private static String[] colors = {"red", "blue", "green", "purple", "yellow", "brown", "azure",
"gray", "ivory", "lime", "navy", "oliver", "coral"};
public Set<Integer> getPoints() {
Set<Integer> points = neighbors.keySet().stream().collect(Collectors.toCollection(HashSet::new));
this.neighbors.values().forEach(i -> points.addAll(i));
return points;
}
public int size() {
return getPoints().size();
}
public long edgeSize() {
return neighbors.values().stream().collect(Collectors.summingLong(Set::size));
}
public void addEdge(int a, int b) {
neighbors.computeIfAbsent(a, k -> new HashSet<Integer>()).add(b);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(a);
}
public void cc() {
neighbors.keySet().stream().forEach(i -> unionFind.put(i, i));
neighbors.keySet().stream().forEach(i -> uFSize.put(i, 1));
for(Integer s : neighbors.keySet()) {
if(!marked.contains(s)) {
bfs(s);
count++;
}
}
}
private void bfs(Integer s) {
Queue<Integer> queue = new LinkedList<>();
marked.add(s);
queue.add(s);
while(!queue.isEmpty()) {
Integer v = queue.poll();
if(neighbors.get(v) == null) continue;
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
marked.add(w);
queue.add(w);
unionFind.put(w, v); //add w to the union v belongs to
} else {
union(unionFind.get(w), unionFind.get(v)); //combine the union w and v belong to
}
}
}
}
private void union(Integer w, Integer v) {
Integer rootp = w;
Integer rootq = v;
for(rootp = w; !unionFind.get(rootp).equals(rootp); rootp = unionFind.get(rootp));
for(rootq = v; !unionFind.get(rootq).equals(rootq); rootq = unionFind.get(rootq));
if(rootp.equals(rootq)) return;
if(uFSize.get(rootp) > uFSize.get(rootq)) {
unionFind.put(rootq, rootp);
uFSize.put(rootp, uFSize.get(rootp) + uFSize.get(rootq));
} else {
unionFind.put(rootp, rootq);
uFSize.put(rootq, uFSize.get(rootp) + uFSize.get(rootq));
}
count--;
}
private Integer find(Integer w) {
Integer p = w;
for(p = w; !p.equals(unionFind.get(p)); p = unionFind.get(p));
return p;
}
public static void main(String...args) {
Digraph g = new Digraph();
//change the number of points and edges here.
for(int i = 0; i < 7; i++) {
g.addEdge(i, i + 1);
g.addEdge(i, i + 2);
}
for(int i = 15; i < 17; i++) {
g.addEdge(i, i+1);
}
g.addEdge(19, 19);
//form circles
g.addEdge(7, 5);
g.addEdge(7, 1);
g.cc();
System.out.println("strict digraph {");
g.neighbors.keySet().stream().forEach(i ->
{
Stream.of(g.neighbors.get(i)).flatMap(j -> j.stream())
.forEach(k -> {
Integer root = g.find(k);
String color = colors[root%colors.length];
System.out.println(i + "->" + k + "[label=" + root
+ ", color=" + color + "];");
});
});
System.out.println("}");
System.out.println("number of points: " + g.size());
System.out.println("number of edges: " + g.edgeSize());
System.out.println("connected components:" + g.count);
}
}
