-
Notifications
You must be signed in to change notification settings - Fork 0
/
provinces.js
46 lines (40 loc) · 1.1 KB
/
provinces.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const getEdges = (idx, edge) => {
const edges = []
for(let i=0; i<edge.length; i++){
if(idx === i) continue
if(edge[i]===0) continue
edges.push(i)
}
return edges
}
const buildAdjList = (edges, n=edges.length) => {
const adjList = Array.from({length: n}, () => [])
console.log(adjList)
for (let i=0; i < edges.length; i++){
adjList[i].push(...getEdges(i, edges[i]))
}
return adjList
}
const dfs = (node, adjList, visited) => {
visited[node] = true;
for (let neighbor of adjList[node]){
if(!visited[neighbor]){
visited[neighbor] = true;
dfs(neighbor, adjList, visited)
}
}
}
const findCircleNum = (isConnected) => {
const adjList = buildAdjList(isConnected)
const visited = {}
let provinces =0
for (let vertex = 0; vertex < adjList.length; vertex++){
if(!visited[vertex]){
provinces++
dfs(vertex, adjList, visited)
}
}
return provinces
}
let isConnected = [[1, 1, 0], [1,1,0], [0,0,1]]
console.log(findCircleNum(isConnected))