Posts tagged as “union find”

花花酱 LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

By zxi on June 26, 2020

Given a weighted undirected connected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between nodes from_i and to_i. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. A pseudo-critical edge, on the other hand, is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i <= 1000
All pairs (from_i, to_i) are distinct.

Solution: Brute Force?

For each edge
1. exclude it and build a MST, cost increased => critical
2. for a non critical edge, force include it and build a MST, cost remains the same => pseudo critical

Proof of 2, if a non critical / non pseudo critical edge was added into the MST, the total cost must be increased. So if the cost remains the same, must be the other case. Since we know the edge is non-critical, so it has to be pseudo critical.

C++

// Author: Huahua

class UnionFind {

public:

explicit UnionFind(int n): p_(n), r_(n) { iota(begin(p_), end(p_), 0); } // e.g. p[i] = i

int Find(int x) { return p_[x] == x ? x : p_[x] = Find(p_[x]); }

bool Union(int x, int y) {

int rx = Find(x);

int ry = Find(y);

if (rx == ry) return false;

if (r_[rx] == r_[ry]) {

p_[rx] = ry;

++r_[ry];

} else if (r_[rx] > r_[ry]) {

p_[ry] = rx;

} else {

p_[rx] = ry;

}

return true;

}

private:

vector<int> p_, r_;

};

class Solution {

public:

vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {

// Record the original id.

for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);

// Sort edges by weight.

sort(begin(edges), end(edges), [&](const auto& e1, const auto& e2){

if (e1[2] != e2[2]) return e1[2] < e2[2];

return e1 < e2;

});

// Cost of MST, ex: edge to exclude, in: edge to include.

auto MST = [&](int ex = -1, int in = -1) -> int {

UnionFind uf(n);

int cost = 0;

int count = 0;

if (in >= 0) {

cost += edges[in][2];

uf.Union(edges[in][0], edges[in][1]);

count++;

}

for (int i = 0; i < edges.size(); ++i) {

if (i == ex) continue;

if (!uf.Union(edges[i][0], edges[i][1])) continue;

cost += edges[i][2];

++count;

}

return count == n - 1 ? cost : INT_MAX;

};

const int min_cost = MST();

vector<int> criticals;

vector<int> pseudos;

for (int i = 0; i < edges.size(); ++i) {

// Cost increased or can't form a tree.

if (MST(i) > min_cost) {

criticals.push_back(edges[i][3]);

} else if (MST(-1, i) == min_cost) {

pseudos.push_back(edges[i][3]);

}

return {criticals, pseudos};

}

};

花花酱 LeetCode 721. Accounts Merge

By zxi on January 29, 2020

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].

Solution: Union-Find

C++

// Author: Huahua

class Solution {

public:

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {

unordered_map<string_view, int> ids; // email to id

unordered_map<int, string_view> names; // id to name

vector<int> p(10000);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

if (p[x] != x) p[x] = find(p[x]);

return p[x];

};

auto getIdByEmail = [&](string_view email) {

auto it = ids.find(email);

if (it == ids.end()) {

int id = ids.size();

return ids[email] = id;

}

return it->second;

};

for (const auto& account : accounts) {

int u = find(getIdByEmail(account[1]));

for (int i = 2; i < account.size(); ++i)

p[find(u)] = find(getIdByEmail(account[i]));

names[find(u)] = string_view(account[0]);

}

unordered_map<int, set<string>> mergered;

for (const auto& account : accounts)

for (int i = 1; i < account.size(); ++i) {

int id = find(getIdByEmail(account[i]));

mergered[id].insert(account[i]);

}

vector<vector<string>> ans;

for (const auto& kv : mergered) {

ans.push_back({string(names[kv.first])});

ans.back().insert(ans.back().end(), kv.second.begin(), kv.second.end());

}

return ans;

}

};

花花酱 LeetCode 1319. Number of Operations to Make Network Connected

By zxi on January 11, 2020

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)

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& c : connections)

p[find(c[0])] = find(c[1]);

unordered_set<int> s;

for (int i = 0; i < n; ++i)

s.insert(find(i));

return s.size() - 1;

}

};

Solution 2: DFS

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

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<vector<int>> g(n);

for (const auto& c : connections) {

g[c[0]].push_back(c[1]);

g[c[1]].push_back(c[0]);

}

vector<int> seen(n);

int count = 0;

function<void(int)> dfs = [&](int cur) {

for (int nxt : g[cur])

if (!seen[nxt]++) dfs(nxt);

};

for (int i = 0; i < n; ++i)

if (!seen[i]++ && ++count)

dfs(i);

return count - 1;

}

};

花花酱 LeetCode 1202. Smallest String With Swaps

By zxi on September 22, 2019

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++/DFS

// Author: Huahua, 268 ms, 89 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

vector<vector<int>> g(s.length());

for (const auto& e : pairs) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

unordered_set<int> seen;

vector<int> idx;

string tmp;

function<void(int)> dfs = [&](int cur) {

if (seen.count(cur)) return;

seen.insert(cur);

idx.push_back(cur);

tmp += s[cur];

for (int nxt : g[cur]) dfs(nxt);

};

for (int i = 0; i < s.length(); ++i) {

if (seen.count(i)) continue;

idx.clear();

tmp.clear();

dfs(i);

sort(begin(tmp), end(tmp));

sort(begin(idx), end(idx));

for (int k = 0; k < idx.size(); ++k)

s[idx[k]] = tmp[k];

}

return s;

}

};

C++/Union-Find

// Author: Huahua, 152 ms, 48.2 MB

class Solution {

public:

string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {

int n = s.length();

vector<int> p(n);

iota(begin(p), end(p), 0); // p = {0, 1, 2, ... n - 1}

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& e : pairs)

p[find(e[0])] = find(e[1]); // union

vector<vector<int>> idx(n);

vector<string> ss(n);

for (int i = 0; i < s.length(); ++i) {

int id = find(i);

idx[id].push_back(i); // already sorted

ss[id].push_back(s[i]);

}

for (int i = 0; i < n; ++i) {

sort(begin(ss[i]), end(ss[i]));

for (int k = 0; k < idx[i].size(); ++k)

s[idx[i][k]] = ss[i][k];

}

return s;

}

};

花花酱 LeetCode 990. Satisfiability of Equality Equations

By zxi on February 10, 2019

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 <= equations.length <= 500
equations[i].length == 4
equations[i][0] and equations[i][3] are lowercase letters
equations[i][1] is either '=' or '!'
equations[i][2] is '='

Solution: Union Find

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

C++

// Author: Huahua, running time: 12 ms, 7.1 MB

class Solution {

public:

bool equationsPossible(vector<string>& equations) {

iota(begin(parents_), end(parents_), 0);

for (const auto& eq : equations)

if (eq[1] == '=')

parents_[find(eq[0])] = find(eq[3]);

for (const auto& eq : equations)

if (eq[1] == '!' && find(eq[0]) == find(eq[3]))

return false;

return true;

}

private:

array<int, 128> parents_;

int find(int x) {

if (x != parents_[x])

parents_[x] = find(parents_[x]);

return parents_[x];

}

};