Commit2df6502

authored

Merge pull requestneetcode-gh#3476 from matthewkeck/Create-0127-word-ladder

Create: 0127-word-ladder.dart

2 parentsbc21316 +d9147b6 commit2df6502Copy full SHA for 2df6502

File tree

+48

-0

lines changed

+48

-0

lines changed

Lines changed: 48 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,48 @@`
	`1`	`+classSolution {`
	`2`	`+List<int>findRedundantConnection(List<List<int>> edges) {`
	`3`	`+List<int> parent= [];`
	`4`	`+for (int i=0; i< edges.length+1; i++) {`
	`5`	`+ parent.add(i);`
	`6`	`+ }`
	`7`	`+`
	`8`	`+List<int> sizes=List.filled(edges.length+1,1);`
	`9`	`+`
	`10`	`+intfind(int n) {`
	`11`	`+int p= parent[n];`
	`12`	`+`
	`13`	`+while (p!= parent[p]) {`
	`14`	`+ parent[p]= parent[parent[p]];`
	`15`	`+ p= parent[p];`
	`16`	`+ }`
	`17`	`+`
	`18`	`+return p;`
	`19`	`+ }`
	`20`	`+`
	`21`	`+boolunion(int node1,int node2) {`
	`22`	`+int parentOf1=find(node1);`
	`23`	`+int parentOf2=find(node2);`
	`24`	`+`
	`25`	`+if (parentOf1== parentOf2) {`
	`26`	`+returnfalse;`
	`27`	`+ }elseif (sizes[parentOf1]> sizes[parentOf2]) {`
	`28`	`+ parent[parentOf2]= parentOf1;`
	`29`	`+ sizes[parentOf1]+= sizes[parentOf2];`
	`30`	`+ }else {`
	`31`	`+ parent[parentOf1]= parentOf2;`
	`32`	`+ sizes[parentOf2]+= sizes[parentOf1];`
	`33`	`+ }`
	`34`	`+`
	`35`	`+returntrue;`
	`36`	`+ }`
	`37`	`+`
	`38`	`+for (List<int> edgein edges) {`
	`39`	`+int node1= edge[0];`
	`40`	`+int node2= edge[1];`
	`41`	`+if (!union(node1, node2)) {`
	`42`	`+return [node1, node2];`
	`43`	`+ }`
	`44`	`+ }`
	`45`	`+`
	`46`	`+return [];`
	`47`	`+ }`
	`48`	`+}`

Comments

(0)