cc4 graphs

import java.util.*;
import java.util.regex.*;

public class GraphTraversal {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();
    private String priorityRule = "HVF";

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    private void applyPriority() {
        for (List<Integer> neighbors : adjList.values()) {
            if (priorityRule.equalsIgnoreCase("HVF")) {
                Collections.sort(neighbors, Collections.reverseOrder());
            } else {
                Collections.sort(neighbors); // LVF
            }
        }
    }

    public void runDFS(int start) {
        Set<Integer> visited = new LinkedHashSet<>();
        List<Integer> result = new ArrayList<>();
        dfsRecursive(start, visited, result);
        System.out.println("DFS: " + formatOutput(result));
    }

    private void dfsRecursive(int node, Set<Integer> visited, List<Integer> result) {
        visited.add(node);
        result.add(node);
        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited, result);
            }
        }
    }

    public void runBFS(int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new LinkedHashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        System.out.println("BFS: " + formatOutput(result));
    }

    private String formatOutput(List<Integer> list) {
        return list.toString().replaceAll("[\\[\\]]", "");
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        GraphTraversal graph = new GraphTraversal();

        System.out.println("Enter edges as (u, v). Type 'done' to stop:");
        
        // This pattern looks for pairs of numbers inside parentheses or separated by commas
        Pattern p = Pattern.compile("(\\d+)\\s*,\\s*(\\d+)");

        while (true) {
            String line = sc.nextLine();
            if (line.equalsIgnoreCase("done")) break;
            
            Matcher m = p.matcher(line);
            while (m.find()) {
                int u = Integer.parseInt(m.group(1));
                int v = Integer.parseInt(m.group(2));
                graph.addEdge(u, v);
            }
        }

        System.out.print("Priority (HVF/LVF): ");
        graph.priorityRule = sc.nextLine().trim();
        
        System.out.print("Starting Point: ");
        if (sc.hasNextInt()) {
            int startNode = sc.nextInt();
            graph.applyPriority();
            System.out.println("\n--- Results ---");
            graph.runDFS(startNode);
            graph.runBFS(startNode);
        }
        
        sc.close();
    }
}