import java.util.*;
?
/**
 * 無向圖的實(shí)現(xiàn)（使用鄰接表）
 */
public class UndirectedGraph {
    // 使用HashMap存儲(chǔ)圖，key為頂點(diǎn)，value為鄰接頂點(diǎn)列表
    private Map<String, List<String>> adjList;
    
    public UndirectedGraph() {
        this.adjList = new HashMap<>();
    }
    
    /**
     * 添加頂點(diǎn)
     */
    public void addVertex(String vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }
    
    /**
     * 添加邊（無向邊，需要雙向添加）
     */
    public void addEdge(String v1, String v2) {
        // 確保兩個(gè)頂點(diǎn)都存在
        addVertex(v1);
        addVertex(v2);
        
        // 添加雙向邊
        adjList.get(v1).add(v2);
        adjList.get(v2).add(v1);
    }
    
    /**
     * 移除邊
     */
    public void removeEdge(String v1, String v2) {
        List<String> v1Neighbors = adjList.get(v1);
        List<String> v2Neighbors = adjList.get(v2);
        
        if (v1Neighbors != null) {
            v1Neighbors.remove(v2);
        }
        if (v2Neighbors != null) {
            v2Neighbors.remove(v1);
        }
    }
    
    /**
     * 移除頂點(diǎn)
     */
    public void removeVertex(String vertex) {
        // 移除所有與該頂點(diǎn)相連的邊
        List<String> neighbors = adjList.get(vertex);
        if (neighbors != null) {
            for (String neighbor : new ArrayList<>(neighbors)) {
                removeEdge(vertex, neighbor);
            }
        }
        // 移除頂點(diǎn)
        adjList.remove(vertex);
    }
    
    /**
     * 獲取頂點(diǎn)的度（連接的邊的數(shù)量）
     */
    public int getDegree(String vertex) {
        List<String> neighbors = adjList.get(vertex);
        return neighbors != null ? neighbors.size() : 0;
    }
    
    /**
     * 獲取鄰接頂點(diǎn)
     */
    public List<String> getNeighbors(String vertex) {
        return adjList.getOrDefault(vertex, new ArrayList<>());
    }
    
    /**
     * 深度優(yōu)先搜索（DFS）
     */
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        dfsHelper(start, visited);
    }
    
    private void dfsHelper(String vertex, Set<String> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        
        for (String neighbor : getNeighbors(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }
    
    /**
     * 廣度優(yōu)先搜索（BFS）
     */
    public void bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        visited.add(start);
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (String neighbor : getNeighbors(vertex)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    /**
     * 打印圖結(jié)構(gòu)
     */
    public void display() {
        System.out.println("無向圖結(jié)構(gòu)：");
        for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

public class UndirectedGraphDemo {
    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph();
        
        // 構(gòu)建社交網(wǎng)絡(luò)
        graph.addEdge("Alice", "Bob");
        graph.addEdge("Alice", "Charlie");
        graph.addEdge("Bob", "David");
        graph.addEdge("Charlie", "David");
        graph.addEdge("David", "Eve");
        
        // 顯示圖結(jié)構(gòu)
        graph.display();
        
        System.out.println("\n各頂點(diǎn)的度：");
        System.out.println("Alice的度: " + graph.getDegree("Alice"));
        System.out.println("David的度: " + graph.getDegree("David"));
        
        System.out.println("\n深度優(yōu)先搜索（從Alice開始）：");
        graph.dfs("Alice");
        
        System.out.println("\n\n廣度優(yōu)先搜索（從Alice開始）：");
        graph.bfs("Alice");
    }
}

import java.util.*;
?
/**
 * 有向圖的實(shí)現(xiàn)（使用鄰接表）
 */
public class DirectedGraph {
    private Map<String, List<String>> adjList;
    
    public DirectedGraph() {
        this.adjList = new HashMap<>();
    }
    
    /**
     * 添加頂點(diǎn)
     */
    public void addVertex(String vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }
    
    /**
     * 添加有向邊（從v1指向v2）
     */
    public void addEdge(String from, String to) {
        addVertex(from);
        addVertex(to);
        
        // 只添加單向邊
        adjList.get(from).add(to);
    }
    
    /**
     * 移除邊
     */
    public void removeEdge(String from, String to) {
        List<String> neighbors = adjList.get(from);
        if (neighbors != null) {
            neighbors.remove(to);
        }
    }
    
    /**
     * 移除頂點(diǎn)
     */
    public void removeVertex(String vertex) {
        // 移除從該頂點(diǎn)出發(fā)的所有邊
        adjList.remove(vertex);
        
        // 移除指向該頂點(diǎn)的所有邊
        for (List<String> neighbors : adjList.values()) {
            neighbors.remove(vertex);
        }
    }
    
    /**
     * 獲取出度（從該頂點(diǎn)出發(fā)的邊數(shù)）
     */
    public int getOutDegree(String vertex) {
        List<String> neighbors = adjList.get(vertex);
        return neighbors != null ? neighbors.size() : 0;
    }
    
    /**
     * 獲取入度（指向該頂點(diǎn)的邊數(shù)）
     */
    public int getInDegree(String vertex) {
        int count = 0;
        for (List<String> neighbors : adjList.values()) {
            if (neighbors.contains(vertex)) {
                count++;
            }
        }
        return count;
    }
    
    /**
     * 獲取鄰接頂點(diǎn)（出邊指向的頂點(diǎn)）
     */
    public List<String> getNeighbors(String vertex) {
        return adjList.getOrDefault(vertex, new ArrayList<>());
    }
    
    /**
     * 拓?fù)渑判颍↘ahn算法）
     * 適用于有向無環(huán)圖（DAG）
     */
    public List<String> topologicalSort() {
        List<String> result = new ArrayList<>();
        Map<String, Integer> inDegree = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        
        // 計(jì)算所有頂點(diǎn)的入度
        for (String vertex : adjList.keySet()) {
            inDegree.put(vertex, getInDegree(vertex));
        }
        
        // 將入度為0的頂點(diǎn)加入隊(duì)列
        for (Map.Entry<String, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        
        // BFS處理
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            result.add(vertex);
            
            // 減少鄰接頂點(diǎn)的入度
            for (String neighbor : getNeighbors(vertex)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // 如果結(jié)果包含所有頂點(diǎn)，說明沒有環(huán)
        if (result.size() != adjList.size()) {
            System.out.println("圖中存在環(huán)，無法進(jìn)行拓?fù)渑判颍?);
            return new ArrayList<>();
        }
        
        return result;
    }
    
    /**
     * 檢測是否存在環(huán)（使用DFS）
     */
    public boolean hasCycle() {
        Set<String> visited = new HashSet<>();
        Set<String> recStack = new HashSet<>();
        
        for (String vertex : adjList.keySet()) {
            if (hasCycleHelper(vertex, visited, recStack)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean hasCycleHelper(String vertex, Set<String> visited, 
                                   Set<String> recStack) {
        if (recStack.contains(vertex)) {
            return true; // 發(fā)現(xiàn)環(huán)
        }
        if (visited.contains(vertex)) {
            return false;
        }
        
        visited.add(vertex);
        recStack.add(vertex);
        
        for (String neighbor : getNeighbors(vertex)) {
            if (hasCycleHelper(neighbor, visited, recStack)) {
                return true;
            }
        }
        
        recStack.remove(vertex);
        return false;
    }
    
    /**
     * 深度優(yōu)先搜索
     */
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        dfsHelper(start, visited);
    }
    
    private void dfsHelper(String vertex, Set<String> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        
        for (String neighbor : getNeighbors(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }
    
    /**
     * 打印圖結(jié)構(gòu)
     */
    public void display() {
        System.out.println("有向圖結(jié)構(gòu)：");
        for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

public class DirectedGraphDemo {
    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        
        // 構(gòu)建課程依賴關(guān)系圖
        graph.addEdge("數(shù)據(jù)結(jié)構(gòu)", "算法");
        graph.addEdge("離散數(shù)學(xué)", "數(shù)據(jù)結(jié)構(gòu)");
        graph.addEdge("離散數(shù)學(xué)", "算法");
        graph.addEdge("程序設(shè)計(jì)", "數(shù)據(jù)結(jié)構(gòu)");
        graph.addEdge("算法", "人工智能");
        graph.addEdge("數(shù)據(jù)結(jié)構(gòu)", "數(shù)據(jù)庫");
        
        // 顯示圖結(jié)構(gòu)
        graph.display();
        
        System.out.println("\n各頂點(diǎn)的入度和出度：");
        System.out.println("數(shù)據(jù)結(jié)構(gòu) - 入度: " + graph.getInDegree("數(shù)據(jù)結(jié)構(gòu)") + 
                         ", 出度: " + graph.getOutDegree("數(shù)據(jù)結(jié)構(gòu)"));
        System.out.println("算法 - 入度: " + graph.getInDegree("算法") + 
                         ", 出度: " + graph.getOutDegree("算法"));
        
        System.out.println("\n檢測環(huán)：");
        System.out.println("是否存在環(huán): " + graph.hasCycle());
        
        System.out.println("\n拓?fù)渑判颍ㄕn程學(xué)習(xí)順序）：");
        List<String> order = graph.topologicalSort();
        System.out.println(order);
        
        System.out.println("\n深度優(yōu)先搜索（從離散數(shù)學(xué)開始）：");
        graph.dfs("離散數(shù)學(xué)");
    }
}

/**
 * 使用鄰接矩陣實(shí)現(xiàn)的圖（支持有向圖和無向圖）
 */
public class GraphMatrix {
    private int[][] matrix;
    private Map<String, Integer> vertexIndex;
    private Map<Integer, String> indexVertex;
    private int vertexCount;
    private boolean isDirected;
    
    public GraphMatrix(int maxVertices, boolean isDirected) {
        this.matrix = new int[maxVertices][maxVertices];
        this.vertexIndex = new HashMap<>();
        this.indexVertex = new HashMap<>();
        this.vertexCount = 0;
        this.isDirected = isDirected;
    }
    
    /**
     * 添加頂點(diǎn)
     */
    public void addVertex(String vertex) {
        if (!vertexIndex.containsKey(vertex)) {
            vertexIndex.put(vertex, vertexCount);
            indexVertex.put(vertexCount, vertex);
            vertexCount++;
        }
    }
    
    /**
     * 添加邊
     */
    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);
        
        int index1 = vertexIndex.get(v1);
        int index2 = vertexIndex.get(v2);
        
        matrix[index1][index2] = 1;
        
        // 如果是無向圖，需要添加反向邊
        if (!isDirected) {
            matrix[index2][index1] = 1;
        }
    }
    
    /**
     * 檢查是否存在邊
     */
    public boolean hasEdge(String v1, String v2) {
        Integer index1 = vertexIndex.get(v1);
        Integer index2 = vertexIndex.get(v2);
        
        if (index1 == null || index2 == null) {
            return false;
        }
        
        return matrix[index1][index2] == 1;
    }
    
    /**
     * 打印鄰接矩陣
     */
    public void display() {
        System.out.println("鄰接矩陣：");
        System.out.print("    ");
        for (int i = 0; i < vertexCount; i++) {
            System.out.printf("%-8s", indexVertex.get(i));
        }
        System.out.println();
        
        for (int i = 0; i < vertexCount; i++) {
            System.out.printf("%-4s", indexVertex.get(i));
            for (int j = 0; j < vertexCount; j++) {
                System.out.printf("%-8d", matrix[i][j]);
            }
            System.out.println();
        }
    }
}