Algorithme de Karger

Pour le dernier jour, j'ai tenté plusieurs solutions naïve avant de chercher un algorithme qui pouvait répondre à mon problème.

Je suis tombé sur l'algorithme de Karger qui me semblait relativement simple à implémenter.

https://fr.wikipedia.org/wiki/Algorithme_de_Karger

Je trouve que ma condition de sortie est un peu moisie mais dans l'ensemble.
En gros, j'arrête le programme quand j'arrive à une contraction à 2 noeud avec 3 lien qui sont les 3 liens à couper.
C'était la solution attendu. Je n'ai pas cherché plus loin.

package aoc2023;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Aoc2023s25 {
 final static Random random = new Random(0);
 public static class Link {
 String srcName;
 String dstName;
 public Link(String srcName, String dstName) {
 this.srcName = srcName;
 this.dstName = dstName;
 }
 @Override
 public String toString() {
 return dstName + "/" + srcName;
 }
 public boolean match(String name) {
 return name.equals(srcName) || name.equals(dstName);
 }
 public String otherName(String name) {
 return srcName.equals(name) ? dstName : srcName;
 }
 public Link replace(String left, String right, String b) {
 String nsrc = srcName;
 if (nsrc.equals(left) || nsrc.equals(right)) {
 nsrc = b;
 }
 String ndst = dstName;
 if (ndst.equals(left) || ndst.equals(right)) {
 ndst = b;
 }
 return new Link(nsrc, ndst);
 }
 }
 public static class Node {
 String name;
 public Node(String s) {
 this.name = s;
 }
 @Override
 public String toString() {
 return "Node [name=" + name + "]";
 }
 @Override
 public int hashCode() {
 return Objects.hash(name);
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 Node other = (Node) obj;
 return Objects.equals(name, other.name);
 }
 }
 public static void main(String[] args) {
 try (Scanner in = new Scanner(Aoc2023s25.class.getResourceAsStream("res/t25.txt"))) {
 Map<String, Node> nodeByName = new HashMap<>();
 List<Link> links = new ArrayList<>();
 while (in.hasNext()) {
 String row = in.nextLine();
 String[] fields = row.split(":");
 Node n = new Node(fields[0].trim());
 nodeByName.put(n.name, n);
 links.addAll(Arrays.stream(fields[1].trim().split(" ")).map(String::trim)
 .map(d -> new Link(n.name, d)).toList());
 }
 for (Link a : links) {
 nodeByName.computeIfAbsent(a.dstName, k -> new Node(k + ": "));
 }
 while (true) {
 Map<String, Node> clone = new HashMap<>(nodeByName);
 algorithmKarger(clone, new ArrayList<>(links));
 }
 }
 }
 private static void algorithmKarger(Map<String, Node> nodeByName, List<Link> links) {
 while(nodeByName.size() > 2) {
 Link link = links.get(random.nextInt(links.size()));
 String leftName = link.srcName;
 String rightName = link.dstName;
 String contractName = leftName + "," + rightName;
 nodeByName.remove(leftName);
 nodeByName.remove(rightName);
 nodeByName.put(contractName,new Node(contractName));
 List<Link> intLinks = links.stream()
 .filter(l -> !(l.match(leftName) && l.match(rightName)))
 .map(l->l.replace(leftName, rightName, contractName))
 .toList();
 links =intLinks;
 }
 System.out.println(nodeByName.size());
 System.out.println(links.size());
 for(Node n : nodeByName.values()) {
 System.out.println(n.name + " => " + n);
 }
 if(links.size() == 3) {
 int prod = 1;
 for(String n : nodeByName.keySet()) {
 String[] keys = n.split(",");
 System.out.println(keys.length);
 prod *= keys.length;
 }
 System.out.println(prod);
 System.out.println(links);
 System.exit(0);
 }
 }
}