Commit515d9ed

authored

Merge pull requestneetcode-gh#3434 from neetcode-gh/felivalencia3-patch-1

Create 1857-largest-color-value-in-a-directed-graph.rs

2 parentsa889e34 +7d522dd commit515d9edCopy full SHA for 515d9ed

File tree

+51

-0

lines changed

+51

-0

lines changed

Lines changed: 51 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,51 @@`
	`1`	`+use std::collections::VecDeque;`
	`2`	`+`
	`3`	`+implSolution{`
	`4`	`+pubfnlargest_path_value(colors:String,edges:Vec<Vec<i32>>) ->i32{`
	`5`	`+let n = colors.len();`
	`6`	`+letmut graph =vec![vec![]; n];`
	`7`	`+letmut indegree =vec![0; n];`
	`8`	`+`
	`9`	`+for edgein edges{`
	`10`	`+let u = edge[0]asusize;`
	`11`	`+let v = edge[1]asusize;`
	`12`	`+ graph[u].push(v);`
	`13`	`+ indegree[v] +=1;`
	`14`	`+}`
	`15`	`+`
	`16`	`+letmut queue =VecDeque::new();`
	`17`	`+for iin0..n{`
	`18`	`+if indegree[i] ==0{`
	`19`	`+ queue.push_back(i);`
	`20`	`+}`
	`21`	`+}`
	`22`	`+`
	`23`	`+letmut color_count =vec![vec![0;26]; n];`
	`24`	`+letmut visited =0;`
	`25`	`+let colors = colors.as_bytes();`
	`26`	`+letmut max_color_value =0;`
	`27`	`+`
	`28`	`+whileletSome(node) = queue.pop_front(){`
	`29`	`+ visited +=1;`
	`30`	`+let color_index =(colors[node] -b'a')asusize;`
	`31`	`+ color_count[node][color_index] +=1;`
	`32`	`+ max_color_value = max_color_value.max(color_count[node][color_index]);`
	`33`	`+`
	`34`	`+for&neighin&graph[node]{`
	`35`	`+for iin0..26{`
	`36`	`+ color_count[neigh][i] = color_count[neigh][i].max(color_count[node][i]);`
	`37`	`+}`
	`38`	`+ indegree[neigh] -=1;`
	`39`	`+if indegree[neigh] ==0{`
	`40`	`+ queue.push_back(neigh);`
	`41`	`+}`
	`42`	`+}`
	`43`	`+}`
	`44`	`+`
	`45`	`+if visited != nasi32{`
	`46`	`+return -1;`
	`47`	`+}`
	`48`	`+`
	`49`	`+ max_color_value`
	`50`	`+}`
	`51`	`+}`

Comments

(0)