package leetcode.linkTable;
import java.util.*;
import java.util.stream.Collectors;

public class ProjectAnalysis {

    static class Transition {
        int uniqueId;
        int projectNumber;
        String in, out;

        Transition(int uniqueId, int projectNumber, String in, String out) {
            this.uniqueId = uniqueId;
            this.projectNumber = projectNumber;
            this.in = in;
            this.out = out;
        }
    }

    public static void main(String[] args) {
        List<Transition> data = Arrays.asList(
            new Transition(1, 1, "A", "B"), new Transition(2, 2, "H", "I"),
            new Transition(3, 1, "C", "D"), new Transition(4, 1, "B", "C"),
            new Transition(5, 2, "G", "H"), new Transition(6, 3, "M", "N"),
            new Transition(7, 4, "Y", "Z"), new Transition(8, 3, "N", "O"),
            new Transition(9, 4, "X", "Y"), new Transition(10, 1, "E", "F"),
            new Transition(11, 5, "S", "T"), new Transition(12, 5, "T", "U"),
            new Transition(13, 5, "U", "S"), new Transition(14, 6, "V", "W"),
            new Transition(15, 6, "W", "W1"), new Transition(16, 6, "W1", "W2"),
            new Transition(17, 6, "W2", "W")
        );

        Map<Integer, List<Transition>> projects = new TreeMap<>();
        for (Transition t : data) {
            projects.computeIfAbsent(t.projectNumber, k -> new ArrayList<>()).add(t);
        }

        // Sorting transitions within each project by unique ID
        for (List<Transition> list : projects.values()) {
            list.sort(Comparator.comparingInt(t -> t.uniqueId));
        }

        // Analyzing each project and printing the result
        for (Map.Entry<Integer, List<Transition>> entry : projects.entrySet()) {
            int projectNumber = entry.getKey();
            List<Transition> transitions = entry.getValue();
            System.out.println("项目" + projectNumber + ": " + analyzeProject(transitions));
        }
    }

    private static String analyzeProject(List<Transition> transitions) {
        Map<String, String> map = new HashMap<>();
        Set<String> allNodes = new HashSet<>();

        for (Transition t : transitions) {
            map.put(t.in, t.out);
            allNodes.add(t.in);
            allNodes.add(t.out);
        }

        Set<String> visited = new HashSet<>();
        List<String> chains = new ArrayList<>();
        boolean hasCycle = false;
        Set<String> cycleNodes = new HashSet<>();

        // Detect all chains and cycles
        for (String node : allNodes) {
            if (!visited.contains(node) && map.containsKey(node)) {
                List<String> path = new ArrayList<>();
                Set<String> pathNodes = new HashSet<>();
                String current = node;
                while (current != null && !pathNodes.contains(current)) {
                    pathNodes.add(current);
                    path.add(current);
                    current = map.get(current);
                }
                if (current != null && pathNodes.contains(current)) {
                    hasCycle = true; // A cycle is detected
                    int index = path.indexOf(current);
                    List<String> cycle = path.subList(index, path.size());
                    cycle.add(current);
                    chains.add("Cycle: " + String.join(" -> ", cycle));
                    cycleNodes.addAll(cycle);
                } else {
                    chains.add("Chain: " + String.join(" -> ", path));
                }
                visited.addAll(pathNodes);
            }
        }

        // Determine if it's a full cycle, partial cycle or just chains
        if (hasCycle) {
            if (cycleNodes.size() < allNodes.size()) {
                return "中心成圈: " + chains.stream().filter(s -> s.startsWith("Cycle")).findFirst().orElse("");
            } else {
                return "成圈: " + chains.stream().filter(s -> s.startsWith("Cycle")).findFirst().orElse("");
            }
        } else {
            if (chains.size() > 1) {
                return "成链但不全,存在多条链: " + chains.stream().filter(s -> s.startsWith("Chain")).collect(Collectors.joining(", "));
            } else {
                return "成链: " + chains.get(0);
            }
        }
    }
}