# Posts tagged as “union find”

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation:
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'],
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.


Note:The length of accounts will be in the range [1, 1000].The length of accounts[i] will be in the range [1, 10].The length of accounts[i][j] will be in the range [1, 30].

## C++

There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.

Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.


Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2


Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.


Example 4:

Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0


Constraints:

• 1 <= n <= 10^5
• 1 <= connections.length <= min(n*(n-1)/2, 10^5)
• connections[i].length == 2
• 0 <= connections[i][0], connections[i][1] < n
• connections[i][0] != connections[i][1]
• There are no repeated connections.
• No two computers are connected by more than one cable.

## Solution 1: Union-Find

Time complexity: O(V+E)
Space complexity: O(V)

## Solution 2: DFS

Time complexity: O(V+E)
Space complexity: O(V+E)

## C++

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"


Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"



Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

## Solution: Connected Components

Use DFS / Union-Find to find all the connected components of swapable indices. For each connected components (index group), extract the subsequence of corresponding chars as a string, sort it and put it back to the original string in the same location.

e.g. s = “dcab”, pairs = [[0,3],[1,2]]
There are two connected components: {0,3}, {1,2}
subsequences:
1. 0,3 “db”, sorted: “bd”
2. 1,2 “ca”, sorted: “ac”
0 => b
1 => a
2 => c
3 => d
final = “bacd”

Time complexity: DFS: O(nlogn + k*(V+E)), Union-Find: O(nlogn + V+E)
Space complexity: O(n)

## C++/Union-Find

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b".  Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.


Example 2:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.


Example 3:

Input: ["a==b","b==c","a==c"]
Output: true


Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false


Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true


Note:

1. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0] and equations[i][3] are lowercase letters
4. equations[i][1] is either '=' or '!'
5. equations[i][2] is '='

## Solution: Union Find

Time complexity: O(n)
Space complexity: O(1)

## C++

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /\, or blank space.  These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:[  " /",  "/ "]Output: 2Explanation: The 2x2 grid is as follows:

Example 2:

Input:[  " /",  "  "]Output: 1Explanation: The 2x2 grid is as follows:

Example 3:

Input:[  "\/",  "/\"]Output: 4Explanation: (Recall that because \ characters are escaped, "\/" refers to \/, and "/\" refers to /\.)The 2x2 grid is as follows:

Example 4:

Input:[  "/\",  "\/"]Output: 5Explanation: (Recall that because \ characters are escaped, "/\" refers to /\, and "\/" refers to \/.)The 2x2 grid is as follows:

Example 5:

Input:[  "//",  "/ "]Output: 3Explanation: The 2x2 grid is as follows:

Note:

1. 1 <= grid.length == grid[0].length <= 30
2. grid[i][j] is either '/''\', or ' '.

# Solution 1: Split grid into 4 triangles and Union Find Faces

Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)

# Solution 3: Pixelation (Upscale 3 times)

Time complexity: O(n^2)
Space complexity: O(n^2)