[Go] [Golang] DFS, Adjacency List
Since we know that graph is sparse we\'ll use Adjacency List to represent graph.\nn : number of cities\nm: number of roads\nSpace and Time complexity for Adjace
Since we know that graph is sparse we\'ll use Adjacency List to represent graph.\n**n : number of cities**\n**m: number of roads**\n*Space* and *Time* complexity for *Adjacency List* will be: **O(n + m)** [only if graph is sparse]\nIn worst case(i.e. when graph is dense) *space* and *time* complexity will be **n^2.**\n\n### 1. Build an Adjacency List:\nTime to build an Adjacency List will be **O(m)**\n\n![example](https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png)\n\nWe\'ll use `[[0,1],[1,3],[2,3],[4,0],[4,5]]` edges to build list.\n```\nadList := make(map[int][]int)\n\nfor _, con := range connections {\n\t//  Append the outgoing road to the city\n\tadList[con[0]] = append(adList[con[0]], con[1])\n\n\t// Append incoming road to the city.  Here we need a way to differenciate between \n\t// incoming and outgoing road So we can mark this edge negetive. \n\tadList[con[1]] = append(adList[con[1]], -con[0])\n}\n```\n\n<details>\n  <summary>Important Details</summary>\n  \n> **Note that in case of the city `0` negative of `0` will be `0` itself So here we can\'t sure about the direction of the edge. But this won\'t create any issue when we\'ll traverse the graph because we\'re starting DFS from city `0` and marking it as visited.**\n\n</details>\n\n\nAfter building Adjacency List it will look like this: \n```\nmap[\n\t0:[1 -4] \n\t1:[0 3] \n\t2:[3] \n\t3:[-1 -2] \n\t4:[0 5] \n\t5:[-4]\n]\n```\n\n### 2. Keep track of visited nodes:\nTo keep track of visited cities we\'re using a slice. Because the city\'s names are simply from 0 to n-1 so we can directly map these with the slice index. If cities had some name like in the real world then we had to use a map.\n```\nvisited := make([]bool, n)\n```\n\n### 3. Use DFS to traverse the graph:\nHere we\'re using closure to avoid passing the `cities` and count parameters.\n```\nvar dfs func(start int)\ndfs = func(start int) {\n\tvisited[start] = true\n\tfor _, nb := range adList[start] {\n\t\t// incoming edge\n\t\tif nb < 0 { // nb -> neighbor\n\t\t\tnb = abs(nb)\n\t\t\tif !visited[nb] {\n\t\t\t\tdfs(nb)\n\t\t\t}\n\t\t} else {\n\t\t\t// outgoing edge that needs to be reoriented\n\t\t\tif !visited[nb] {\n\t\t\t\tcount++\n\t\t\t\tdfs(nb)\n\t\t\t}\n\t\t}\n\t}\n}\n// start with city `0`\ndfs(0)\n```\n\n## Complete Code\n```\nfunc minReorder(n int, connections [][]int) int {\n\tadList := make(map[int][]int)\n\n\tfor _, con := range connections {\n\t\tadList[con[0]] = append(adList[con[0]], con[1])\n\t\tadList[con[1]] = append(adList[con[1]], -con[0])\n\t}\n\n\tcount := 0\n    visited := make([]bool, n)\n\n\tvar dfs func(start int)\n\tdfs = func(start int) {\n\t\tvisited[start] = true\n\t\tfor _, nb := range adList[start] {\n\t\t\tif nb < 0 {\n\t\t\t\tnb = abs(nb)\n\t\t\t\tif !visited[nb] {\n\t\t\t\t\tdfs(nb)\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif !visited[nb] {\n\t\t\t\t\tcount++\n\t\t\t\t\tdfs(nb)\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tdfs(0)\n\treturn count\n}\n\nfunc abs(a int) int {\n\tif a < 0 {\n\t\treturn -a\n\t}\n\treturn a\n}\n```
['Depth-First Search', 'Go']