package main

import (
	"fmt"
	"errors"
)

type Node struct {
	Key   string
	Edges map[string]*Node // 相鄰節(jié)點
}

type DAG struct {
	Nodes map[string]*Node
}

func NewDAG() *DAG {
	return &DAG{
		Nodes: make(map[string]*Node),
	}
}

func NewNode(key string) *Node {
	return &Node{
		Key:   key,
		Edges: make(map[string]*Node),
	}
}

func (dag *DAG) AddNode(node *Node) {
	dag.Nodes[node.Key] = node
}

func (dag *DAG) AddEdge(from, to string) error {
	fromNode, fromExists := dag.Nodes[from]
	toNode, toExists := dag.Nodes[to]

	if !fromExists || !toExists {
		return errors.New("both nodes must exist")
	}

	// 先假設(shè)邊已經(jīng)添加，用于環(huán)檢測
	fromNode.Edges[to] = toNode

	if dag.hasCycle() {
		delete(fromNode.Edges, to) // 如果檢測到環(huán)，則撤銷添加邊的操作
		return errors.New("adding this edge would create a cycle")
	}

	return nil
}

// 使用深度優(yōu)先搜索（DFS）檢查是否存在環(huán)

func (dag *DAG) hasCycle() bool {
	visited := make(map[string]bool)
	recStack := make(map[string]bool)

	for nodeKey := range dag.Nodes {
		if dag.isCyclicUtil(nodeKey, visited, recStack) {
			return true
		}
	}
	return false
}

func (dag *DAG) isCyclicUtil(nodeKey string, visited, recStack map[string]bool) bool {
	if recStack[nodeKey] {
		return true
	}

	if visited[nodeKey] {
		return false
	}

	visited[nodeKey] = true
	recStack[nodeKey] = true

	node := dag.Nodes[nodeKey]
	for _, adjNode := range node.Edges {
		if dag.isCyclicUtil(adjNode.Key, visited, recStack) {
			return true
		}
	}

	recStack[nodeKey] = false
	return false
}

package main

import (
	"fmt"
)

func main() {
	// 創(chuàng)建一個新的DAG實例
	dag := NewDAG()

	// 創(chuàng)建節(jié)點
	nodeA := NewNode("A")
	nodeB := NewNode("B")
	nodeC := NewNode("C")
	nodeD := NewNode("D")

	// 向DAG中添加節(jié)點
	dag.AddNode(nodeA)
	dag.AddNode(nodeB)
	dag.AddNode(nodeC)
	dag.AddNode(nodeD)

	// 添加邊
	err := dag.AddEdge("A", "B")
	if err != nil {
		fmt.Println("Failed to add edge A->B:", err)
	}
	err = dag.AddEdge("B", "C")
	if err != nil {
		fmt.Println("Failed to add edge B->C:", err)
	}
	err = dag.AddEdge("C", "D")
	if err != nil {
		fmt.Println("Failed to add edge C->D:", err)
	}

	// 嘗試添加一個會造成環(huán)的邊（D -> A）
	err = dag.AddEdge("D", "A")
	if err != nil {
		fmt.Println("Failed to add edge D->A:", err)
	} else {
		fmt.Println("Edge D->A added successfully")
	}

	// 輸出結(jié)果，驗證環(huán)檢測
	fmt.Println("DAG construction completed without cycles.")
}