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 Graph {
private Set<Integer> marked = new HashSet<>();
private Map<Integer, Set<Integer>> neighbors = new HashMap<>();
private Map<Integer, Integer> components = new HashMap<>();
private int count = 0;
private static String[] colors = {"red", "blue", "green", "purple", "yellow", "brown", "azure",
"gray", "ivory", "lime", "navy", "oliver", "coral", "cyan", "pink"};
public Set<Integer> getPoints() {
return neighbors.keySet();
}
public int size() {
return getPoints().size();
}
public long edgeSize() {
return neighbors.values().stream()
.collect(Collectors.summingLong(Set::size)) / 2;
}
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() {
for(Integer s : neighbors.keySet()) {
if(!marked.contains(s)) {
bfs(s);
count ++;
}
}
}
private void bfs(Integer s) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(s);
marked.add(s);
components.put(s, count);
while(!queue.isEmpty()) {
Integer v = queue.poll();
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
marked.add(w);
queue.offer(w);
components.put(w, count);
}
}
}
}
public static void main(String... args) {
Graph g = new Graph();
// 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);
g.cc();
System.out.println("strict graph {");
g.neighbors
.keySet()
.stream()
.forEach(
i -> {
Stream.of(g.neighbors.get(i))
.flatMap(j -> j.stream())
.forEach(
k -> System.out.println(i + "--"
+ k + "[label=" + g.components.get(i)
+ ", color=" + colors[g.components.get(i)%colors.length]
+ "];"));
});
System.out.println("}");
System.out.println("number of points: " + g.size());
System.out.println("number of edges: " + g.edgeSize());
System.out.println("number of connected components: " + g.count);
}
}
