DFS

package main

import (
	"bufio"
	"fmt"
	"io"
	"strconv"
	"strings"
)

type NodeColor int

const (
	White NodeColor = iota
	Grey
	Black
)

type Node struct {
	color         NodeColor
	discoveryTime int
	finishTime    int
	pi            *Node
}

func (n *Node) Reset() {
	n.color = White
	n.discoveryTime = -1
	n.finishTime = -1
	n.pi = nil
}

type Graph struct {
	nodes []*Node
	links map[*Node][]*Node
	time  int
}

func (g *Graph) Reset() {
	g.time = 0
	for _, n := range g.nodes {
		n.Reset()
	}
}

func NewGraph(size int32) *Graph {
	var nodes []*Node
	var i int32
	for i = 0; i < size; i++ {
		nodes = append(nodes, &Node{})
	}

	return &Graph{
		nodes: nodes,
		links: make(map[*Node][]*Node),
	}
}

func (g *Graph) AddLink(link []int32) {
	g.links[g.nodes[link[0]-1]] = append(g.links[g.nodes[link[0]-1]], g.nodes[link[1]-1])
}

func (g *Graph) AddBatchLink(links [][]int32) {
	for _, link := range links {
		g.AddLink(link)
	}
}

func (g *Graph) DFSVis(n *Node, parent *Node) {
	g.time++
	n.discoveryTime = g.time
	n.color = Grey
	n.pi = parent

	for _, child := range g.links[n] {
		if child.color == White {
			g.DFSVis(child, n)
		}
	}
	g.time++
	n.finishTime = g.time
	n.color = Black
}

func (g *Graph) DFS() {
	g.Reset()

	for _, n := range g.nodes {
		if n.color == White {
			g.DFSVis(n, nil)
		}
	}
}

func main() {
	// first line contains the number of nodes N space seperated from the number of links M between nodes
	// the M subsequent lines with the x y format each describe a link from node x to y
	// the last line is the source from which we want to compute the BFS
	input := `4 3
1 2
2 3
1 4
`

	r := strings.NewReader(input)
	reader := bufio.NewReaderSize(r, 1024*1024)

	nm := strings.Split(readLine(reader), " ")

	nTemp, err := strconv.ParseInt(nm[0], 10, 64)
	if err != nil {
		panic(err)
	}
	n := int32(nTemp)

	mTemp, err := strconv.ParseInt(nm[1], 10, 64)
	if err != nil {
		panic(err)
	}
	m := int32(mTemp)

	var links [][]int32
	for linksRowItr := 0; linksRowItr < int(m); linksRowItr++ {
		linksRowTemp := strings.Split(readLine(reader), " ")

		var linksRow []int32
		for _, linksRowItem := range linksRowTemp {
			linksItemTemp, err := strconv.ParseInt(linksRowItem, 10, 64)
			if err != nil {
				panic(err)
			}
			linksItem := int32(linksItemTemp)
			linksRow = append(linksRow, linksItem)
		}

		if len(linksRow) != int(2) {
			panic("Bad input")
		}

		links = append(links, linksRow)
	}

	grph := NewGraph(n)
	grph.AddBatchLink(links)

	grph.DFS()

	for indx, nd := range grph.nodes {
		fmt.Printf("node %d: [%d %d]\n", indx, nd.discoveryTime, nd.finishTime)
	}

}

func readLine(reader *bufio.Reader) string {
	str, _, err := reader.ReadLine()
	if err == io.EOF {
		return ""
	}

	return strings.TrimRight(string(str), "\r\n")
}