Mar 23, 2025 · Mar 11, 2025 · Mar 11, 2025 · Mar 12, 2025 · Mar 12, 2025 · Mar 12, 2025
diff --git a/articles/count-connected-components.md b/articles/count-connected-components.md
 }
 ```

 ```swift
 class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var adj = Array(repeating: [Int](), count: n)
        var visit = Array(repeating: false, count: n)

        for edge in edges {
            let u = edge[0], v = edge[1]
            adj[u].append(v)
            adj[v].append(u)
        }

        func dfs(_ node: Int) {
            for nei in adj[node] {
                if !visit[nei] {
                    visit[nei] = true
                    dfs(nei)
                }
            }
        }

        var res = 0
        for node in 0..<n {
            if !visit[node] {
                visit[node] = true
                dfs(node)
                res += 1
            }
        }

        return res
    }
 }
 ```

 ::tabs-end

 ### Time & Space Complexity
 }
 ```

 ```swift
 class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var adj = Array(repeating: [Int](), count: n)
        var visit = Array(repeating: false, count: n)
        for edge in edges {
            let u = edge[0], v = edge[1]
            adj[u].append(v)
            adj[v].append(u)
        }

        func bfs(_ node: Int) {
            var q = Deque<Int>()
            q.append(node)
            visit[node] = true
            while !q.isEmpty {
                let cur = q.removeFirst()
                for nei in adj[cur] {
                    if !visit[nei] {
                        visit[nei] = true
                        q.append(nei)
                    }
                }
            }
        }

        var res = 0
        for node in 0..<n {
            if !visit[node] {
                bfs(node)
                res += 1
            }
        }
        return res
    }
 }
 ```

 ::tabs-end

 ### Time & Space Complexity
 ```

 ```java
 publicclass DSU {
 class DSU {
    int[] parent;
    int[] rank;

 }
 ```

 ```swift
 class DSU {
    var parent: [Int]
    var rank: [Int]

    init(_ n: Int) {
        parent = Array(0..<n)
        rank = Array(repeating: 1, count: n)
    }

    func find(_ node: Int) -> Int {
        var cur = node
        while cur != parent[cur] {
            parent[cur] = parent[parent[cur]]
            cur = parent[cur]
        }
        return cur
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        let pu = find(u)
        let pv = find(v)
        if pu == pv { return false }
        var rootU = pu
        var rootV = pv
        if rank[rootV] > rank[rootU] {
            swap(&rootU, &rootV)
        }
        parent[rootV] = rootU
        rank[rootU] += rank[rootV]
        return true
    }
 }

 class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        let dsu = DSU(n)
        var res = n
        for edge in edges {
            let u = edge[0], v = edge[1]
            if dsu.union(u, v) {
                res -= 1
            }
        }
        return res
    }
 }
 ```

 ::tabs-end

 ### Time & Space Complexity
diff --git a/articles/foreign-dictionary.md b/articles/foreign-dictionary.md
 }
 ```

 ```swift
 class Solution {
    func foreignDictionary(_ words: [String]) -> String {
        var adj = [Character: Set<Character>]()
        for word in words {
            for char in word {
                if adj[char] == nil {
                    adj[char] = Set<Character>()
                }
            }
        }

        for i in 0..<words.count - 1 {
            let w1 = words[i]
            let w2 = words[i + 1]
            let minLen = min(w1.count, w2.count)
            if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
                return ""
            }
            for j in 0..<minLen {
                let index1 = w1.index(w1.startIndex, offsetBy: j)
                let index2 = w2.index(w2.startIndex, offsetBy: j)
                if w1[index1] != w2[index2] {
                    adj[w1[index1]]?.insert(w2[index2])
                    break
                }
            }
        }

        var visited = [Character: Bool]()
        var res = [Character]()

        func dfs(_ char: Character) -> Bool {
            if let flag = visited[char] {
                return flag
            }
            visited[char] = true
            for neigh in adj[char]! {
                if dfs(neigh) {
                    return true
                }
            }
            visited[char] = false
            res.append(char)
            return false
        }

        for char in adj.keys {
            if dfs(char) {
                return ""
            }
        }

        res.reverse()
        return String(res)
    }
 }
 ```

 ::tabs-end

 ### Time & Space Complexity
 }
 ```

 ```swift
 class Solution {
    func foreignDictionary(_ words: [String]) -> String {
        var adj = [Character: Set<Character>]()
        for word in words {
            for char in word {
                adj[char] = Set<Character>()
            }
        }

        var indegree = [Character: Int]()
        for key in adj.keys {
            indegree[key] = 0
        }

        for i in 0..<words.count - 1 {
            let w1 = words[i]
            let w2 = words[i + 1]
            let minLen = min(w1.count, w2.count)
            if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
                return ""
            }
            let w1Arr = Array(w1)
            let w2Arr = Array(w2)
            for j in 0..<minLen {
                if w1Arr[j] != w2Arr[j] {
                    if !adj[w1Arr[j]]!.contains(w2Arr[j]) {
                        adj[w1Arr[j]]!.insert(w2Arr[j])
                        indegree[w2Arr[j]]! += 1
                    }
                    break
                }
            }
        }

        var q = Deque<Character>()
        for (c, deg) in indegree {
            if deg == 0 {
                q.append(c)
            }
        }

        var res = [Character]()
        while !q.isEmpty {
            let char = q.removeFirst()
            res.append(char)
            for neighbor in adj[char]! {
                indegree[neighbor]! -= 1
                if indegree[neighbor]! == 0 {
                    q.append(neighbor)
                }
            }
        }

        if res.count != indegree.count {
            return ""
        }

        return String(res)
    }
 }
 ```

 ::tabs-end

 ### Time & Space Complexity
Original file line number	Diff line number	Diff line change
Expand Up		@@ -229,6 +229,41 @@ class Solution {
		}
		```

		```swift
		class Solution {
		func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
		var adj = Array(repeating: [Int](), count: n)
		var visit = Array(repeating: false, count: n)

		for edge in edges {
		let u = edge[0], v = edge[1]
		adj[u].append(v)
		adj[v].append(u)
		}

		func dfs(_ node: Int) {
		for nei in adj[node] {
		if !visit[nei] {
		visit[nei] = true
		dfs(nei)
		}
		}
		}

		var res = 0
		for node in 0..<n {
		if !visit[node] {
		visit[node] = true
		dfs(node)
		res += 1
		}
		}

		return res
		}
		}
		```

		::tabs-end

		### Time & Space Complexity
Expand DownExpand Up		@@ -506,6 +541,44 @@ class Solution {
		}
		```

		```swift
		class Solution {
		func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
		var adj = Array(repeating: [Int](), count: n)
		var visit = Array(repeating: false, count: n)
		for edge in edges {
		let u = edge[0], v = edge[1]
		adj[u].append(v)
		adj[v].append(u)
		}

		func bfs(_ node: Int) {
		var q = Deque<Int>()
		q.append(node)
		visit[node] = true
		while !q.isEmpty {
		let cur = q.removeFirst()
		for nei in adj[cur] {
		if !visit[nei] {
		visit[nei] = true
		q.append(nei)
		}
		}
		}
		}

		var res = 0
		for node in 0..<n {
		if !visit[node] {
		bfs(node)
		res += 1
		}
		}
		return res
		}
		}
		```

		::tabs-end

		### Time & Space Complexity
Expand DownExpand Up		@@ -556,7 +629,7 @@ class Solution:
		```

		```java
		publicclass DSU {
		class DSU {
		int[] parent;
		int[] rank;

Expand DownExpand Up		@@ -877,6 +950,55 @@ class Solution {
		}
		```

		```swift
		class DSU {
		var parent: [Int]
		var rank: [Int]

		init(_ n: Int) {
		parent = Array(0..<n)
		rank = Array(repeating: 1, count: n)
		}

		func find(_ node: Int) -> Int {
		var cur = node
		while cur != parent[cur] {
		parent[cur] = parent[parent[cur]]
		cur = parent[cur]
		}
		return cur
		}

		func union(_ u: Int, _ v: Int) -> Bool {
		let pu = find(u)
		let pv = find(v)
		if pu == pv { return false }
		var rootU = pu
		var rootV = pv
		if rank[rootV] > rank[rootU] {
		swap(&rootU, &rootV)
		}
		parent[rootV] = rootU
		rank[rootU] += rank[rootV]
		return true
		}
		}

		class Solution {
		func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
		let dsu = DSU(n)
		var res = n
		for edge in edges {
		let u = edge[0], v = edge[1]
		if dsu.union(u, v) {
		res -= 1
		}
		}
		return res
		}
		}
		```

		::tabs-end

		### Time & Space Complexity
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -405,6 +405,65 @@ class Solution {
		}
		```

		```swift
		class Solution {
		func foreignDictionary(_ words: [String]) -> String {
		var adj = [Character: Set<Character>]()
		for word in words {
		for char in word {
		if adj[char] == nil {
		adj[char] = Set<Character>()
		}
		}
		}

		for i in 0..<words.count - 1 {
		let w1 = words[i]
		let w2 = words[i + 1]
		let minLen = min(w1.count, w2.count)
		if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
		return ""
		}
		for j in 0..<minLen {
		let index1 = w1.index(w1.startIndex, offsetBy: j)
		let index2 = w2.index(w2.startIndex, offsetBy: j)
		if w1[index1] != w2[index2] {
		adj[w1[index1]]?.insert(w2[index2])
		break
		}
		}
		}

		var visited = [Character: Bool]()
		var res = [Character]()

		func dfs(_ char: Character) -> Bool {
		if let flag = visited[char] {
		return flag
		}
		visited[char] = true
		for neigh in adj[char]! {
		if dfs(neigh) {
		return true
		}
		}
		visited[char] = false
		res.append(char)
		return false
		}

		for char in adj.keys {
		if dfs(char) {
		return ""
		}
		}

		res.reverse()
		return String(res)
		}
		}
		```

		::tabs-end

		### Time & Space Complexity
Expand DownExpand Up		@@ -823,6 +882,69 @@ class Solution {
		}
		```

		```swift
		class Solution {
		func foreignDictionary(_ words: [String]) -> String {
		var adj = [Character: Set<Character>]()
		for word in words {
		for char in word {
		adj[char] = Set<Character>()
		}
		}

		var indegree = [Character: Int]()
		for key in adj.keys {
		indegree[key] = 0
		}

		for i in 0..<words.count - 1 {
		let w1 = words[i]
		let w2 = words[i + 1]
		let minLen = min(w1.count, w2.count)
		if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
		return ""
		}
		let w1Arr = Array(w1)
		let w2Arr = Array(w2)
		for j in 0..<minLen {
		if w1Arr[j] != w2Arr[j] {
		if !adj[w1Arr[j]]!.contains(w2Arr[j]) {
		adj[w1Arr[j]]!.insert(w2Arr[j])
		indegree[w2Arr[j]]! += 1
		}
		break
		}
		}
		}

		var q = Deque<Character>()
		for (c, deg) in indegree {
		if deg == 0 {
		q.append(c)
		}
		}

		var res = [Character]()
		while !q.isEmpty {
		let char = q.removeFirst()
		res.append(char)
		for neighbor in adj[char]! {
		indegree[neighbor]! -= 1
		if indegree[neighbor]! == 0 {
		q.append(neighbor)
		}
		}
		}

		if res.count != indegree.count {
		return ""
		}

		return String(res)
		}
		}
		```

		::tabs-end

		### Time & Space Complexity
Expand Down