Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcbf4fb2

Browse files
authored
Sri Hari: Batch-3/Neetcode-150/Added Golang, Kotlin (neetcode-gh#3739)
* Added Golang, Kotlin* Added Golang, Kotlin
1 parentf2facdc commitcbf4fb2

11 files changed

+1960
-1
lines changed

‎articles/count-connected-components.md‎

Lines changed: 236 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -165,6 +165,70 @@ public class Solution {
165165
}
166166
```
167167

168+
```go
169+
funccountComponents(nint,edges [][]int)int {
170+
adj:=make([][]int, n)
171+
visit:=make([]bool, n)
172+
for_,edge:=range edges {
173+
u,v:= edge[0], edge[1]
174+
adj[u] =append(adj[u], v)
175+
adj[v] =append(adj[v], u)
176+
}
177+
178+
vardfsfunc(int)
179+
dfs =func(nodeint) {
180+
for_,nei:=range adj[node] {
181+
if !visit[nei] {
182+
visit[nei] =true
183+
dfs(nei)
184+
}
185+
}
186+
}
187+
188+
res:=0
189+
fornode:=0; node < n; node++ {
190+
if !visit[node] {
191+
visit[node] =true
192+
dfs(node)
193+
res++
194+
}
195+
}
196+
return res
197+
}
198+
```
199+
200+
```kotlin
201+
classSolution {
202+
funcountComponents(n:Int,edges:Array<IntArray>):Int {
203+
val adj=Array(n) { mutableListOf<Int>() }
204+
val visit=BooleanArray(n)
205+
for ((u, v)in edges) {
206+
adj[u].add(v)
207+
adj[v].add(u)
208+
}
209+
210+
fundfs(node:Int) {
211+
for (neiin adj[node]) {
212+
if (!visit[nei]) {
213+
visit[nei]=true
214+
dfs(nei)
215+
}
216+
}
217+
}
218+
219+
var res=0
220+
for (nodein0 until n) {
221+
if (!visit[node]) {
222+
visit[node]=true
223+
dfs(node)
224+
res++
225+
}
226+
}
227+
return res
228+
}
229+
}
230+
```
231+
168232
::tabs-end
169233

170234
###Time & Space Complexity
@@ -369,6 +433,79 @@ public class Solution {
369433
}
370434
```
371435

436+
```go
437+
funccountComponents(nint,edges [][]int)int {
438+
adj:=make([][]int, n)
439+
visit:=make([]bool, n)
440+
for_,edge:=range edges {
441+
u,v:= edge[0], edge[1]
442+
adj[u] =append(adj[u], v)
443+
adj[v] =append(adj[v], u)
444+
}
445+
446+
bfs:=func(nodeint) {
447+
q:= []int{node}
448+
visit[node] =true
449+
forlen(q) >0 {
450+
cur:= q[0]
451+
q = q[1:]
452+
for_,nei:=range adj[cur] {
453+
if !visit[nei] {
454+
visit[nei] =true
455+
q =append(q, nei)
456+
}
457+
}
458+
}
459+
}
460+
461+
res:=0
462+
fornode:=0; node < n; node++ {
463+
if !visit[node] {
464+
bfs(node)
465+
res++
466+
}
467+
}
468+
return res
469+
}
470+
```
471+
472+
```kotlin
473+
classSolution {
474+
funcountComponents(n:Int,edges:Array<IntArray>):Int {
475+
val adj=Array(n) { mutableListOf<Int>() }
476+
val visit=BooleanArray(n)
477+
for ((u, v)in edges) {
478+
adj[u].add(v)
479+
adj[v].add(u)
480+
}
481+
482+
funbfs(node:Int) {
483+
val q:Queue<Int>=LinkedList()
484+
q.offer(node)
485+
visit[node]=true
486+
while (q.isNotEmpty()) {
487+
val cur= q.poll()
488+
for (neiin adj[cur]) {
489+
if (!visit[nei]) {
490+
visit[nei]=true
491+
q.offer(nei)
492+
}
493+
}
494+
}
495+
}
496+
497+
var res=0
498+
for (nodein0 until n) {
499+
if (!visit[node]) {
500+
bfs(node)
501+
res++
502+
}
503+
}
504+
return res
505+
}
506+
}
507+
```
508+
372509
::tabs-end
373510

374511
###Time & Space Complexity
@@ -641,6 +778,105 @@ public class Solution {
641778
}
642779
```
643780

781+
```go
782+
typeDSUstruct {
783+
parent []int
784+
rank []int
785+
}
786+
787+
funcNewDSU(nint) *DSU {
788+
dsu:= &DSU{
789+
parent:make([]int, n),
790+
rank:make([]int, n),
791+
}
792+
fori:=0; i < n; i++ {
793+
dsu.parent[i] = i
794+
dsu.rank[i] =1
795+
}
796+
return dsu
797+
}
798+
799+
func(dsu *DSU)Find(nodeint)int {
800+
cur:= node
801+
for cur != dsu.parent[cur] {
802+
dsu.parent[cur] = dsu.parent[dsu.parent[cur]]
803+
cur = dsu.parent[cur]
804+
}
805+
return cur
806+
}
807+
808+
func(dsu *DSU)Union(u,vint)bool {
809+
pu:= dsu.Find(u)
810+
pv:= dsu.Find(v)
811+
if pu == pv {
812+
returnfalse
813+
}
814+
if dsu.rank[pv] > dsu.rank[pu] {
815+
pu, pv = pv, pu
816+
}
817+
dsu.parent[pv] = pu
818+
dsu.rank[pu] += dsu.rank[pv]
819+
returntrue
820+
}
821+
822+
funccountComponents(nint,edges [][]int)int {
823+
dsu:=NewDSU(n)
824+
res:= n
825+
for_,edge:=range edges {
826+
u,v:= edge[0], edge[1]
827+
if dsu.Union(u, v) {
828+
res--
829+
}
830+
}
831+
return res
832+
}
833+
```
834+
835+
```kotlin
836+
classDSU(n:Int) {
837+
val parent=IntArray(n) { it }
838+
val rank=IntArray(n) {1 }
839+
840+
funfind(node:Int):Int {
841+
var cur= node
842+
while (cur!= parent[cur]) {
843+
parent[cur]= parent[parent[cur]]
844+
cur= parent[cur]
845+
}
846+
return cur
847+
}
848+
849+
fununion(u:Int,v:Int):Boolean {
850+
val pu= find(u)
851+
val pv= find(v)
852+
if (pu== pv) {
853+
returnfalse
854+
}
855+
if (rank[pv]> rank[pu]) {
856+
parent[pu]= pv
857+
}else {
858+
parent[pv]= pu
859+
rank[pu]+= rank[pv]
860+
}
861+
returntrue
862+
}
863+
}
864+
865+
classSolution {
866+
funcountComponents(n:Int,edges:Array<IntArray>):Int {
867+
val dsu=DSU(n)
868+
var res= n
869+
for (edgein edges) {
870+
val (u, v)= edge
871+
if (dsu.union(u, v)) {
872+
res--
873+
}
874+
}
875+
return res
876+
}
877+
}
878+
```
879+
644880
::tabs-end
645881

646882
###Time & Space Complexity

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp