Posts published in “Graph”

花花酱 LeetCode 996. Number of Squareful Arrays

By zxi on February 17, 2019

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solution1: DFS

Try all permutations with pruning.

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

C++

// Author: Huahua, running time: 4 ms, 8.8 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

std::sort(begin(A), end(A));

vector<int> cur;

vector<int> used(A.size());

int ans = 0;

dfs(A, cur, used, ans);

return ans;

}

private:

bool squareful(int x, int y) {

int s = sqrt(x + y);

return s * s == x + y;

}

void dfs(const vector<int>& A, vector<int>& cur, vector<int>& used, int& ans) {

if (cur.size() == A.size()) {

++ans;

return;

}

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

if (used[i]) continue;

// Avoid duplications.

if (i > 0 && !used[i - 1] && A[i] == A[i - 1]) continue;

// Prune invalid solutions.

if (!cur.empty() && !squareful(cur.back(), A[i])) continue;

cur.push_back(A[i]);

used[i] = 1;

dfs(A, cur, used, ans);

used[i] = 0;

cur.pop_back();

}

};

Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

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

C++

// Author: Huahua, running time: 20 ms, 14.9 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

const int n = A.size();

// For deduplication.

std::sort(begin(A), end(A));

// g[i][j] == 1 if A[i], A[j] are squareful.

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

// dp[s][i] := number of ways to reach state s and ends with node i.

vector<vector<int>> dp(1 << n, vector<int>(n));

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

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

if (i == j) continue;

int r = sqrt(A[i] + A[j]);

if (r * r == A[i] + A[j])

g[i][j] = 1;

}

// For the same numbers, only the first one can be the starting point.

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

if (i == 0 || A[i] != A[i - 1])

dp[(1 << i)][i] = 1;

int ans = 0;

for (int s = 0; s < (1 << n); ++s)

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

if (!dp[s][i]) continue;

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

if (!g[i][j]) continue;

if (s & (1 << j)) continue;

// Only the first one can be used as the dest.

if (j > 0 && !(s & (1 << (j - 1))) && A[j - 1] == A[j]) continue;

dp[s | (1 << j)][j] += dp[s][i];

}

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

ans += dp[(1 << n) - 1][i];

return ans;

}

};

花花酱 LeetCode 133. Clone Graph

By zxi on February 13, 2019

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution: Queue + Hashtable

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

C++

// Author: Huahua, 44ms, 16.8MB

class Solution {

public:

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

if (!node) return nullptr;

typedef UndirectedGraphNode Node;

unordered_set<Node*> done;

unordered_map<Node*, Node*> m;

queue<Node*> q;

q.push(node);

while (!q.empty()) {

Node* s = q.front(); q.pop();

if (done.count(s)) continue;

done.insert(s);

if (!m.count(s))

m[s] = new Node(s->label);

Node* t = m[s];

for (Node* ss : s->neighbors) {

if (!m.count(ss))

m[ss] = new Node(ss->label);

q.push(ss);

t->neighbors.push_back(m[ss]);

}

return m[node];

}

};

花花酱 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];

}

};

花花酱 LeetCode 959. Regions Cut By Slashes

By zxi on December 18, 2018

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: 2
Explanation: The 2x2 grid is as follows:

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Note:

1 <= grid.length == grid[0].length <= 30
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)

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

DSU dsu(4 * n * n);

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

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

int index = 4 * (r * n + c);

switch (grid[r][c]) {

case '/':

dsu.merge(index + 0, index + 3);

dsu.merge(index + 1, index + 2);

break;

case '\\':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 2, index + 3);

break;

case ' ':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 1, index + 2);

dsu.merge(index + 2, index + 3);

break;

default: break;

}

if (r + 1 < n)

dsu.merge(index + 2, index + 4 * n + 0);

if (c + 1 < n)

dsu.merge(index + 1, index + 4 + 3);

}

int ans = 0;

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

if (dsu.find(i) == i) ++ans;

return ans;

}

private:

class DSU {

public:

DSU(int n): parent_(n) {

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

parent_[i] = i;

}

int find(int x) {

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

return parent_[x];

}

void merge(int x, int y) {

parent_[find(x)] = find(y);

}

private:

vector<int> parent_;

};

Solution 2: Euler’s Formula / Union-Find vertices

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

p_ = vector<int>((n + 1) * (n + 1));

// All vertices on the boundaries are merged into root(0).

for (int r = 0; r < n + 1; ++r)

for (int c = 0; c < n + 1; ++c)

p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c);

int f = 1;

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

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

if (grid[r][c] == ' ') continue;

// A new face will created if two vertices are already in the same group.

if (grid[r][c] == '/') {

f += merge(getIndex(n, r, c + 1),

getIndex(n, r + 1, c));

} else {

f += merge(getIndex(n, r, c),

getIndex(n, r + 1, c + 1));

}

return f;

}

private:

vector<int> p_;

int getIndex(int n, int r, int c) { return r * (n + 1) + c; }

int find(int x) {

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

return p_[x];

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[ry] = rx;

return 0;

}

};

Solution 3: Pixelation (Upscale 3 times)

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

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

const int n = grid.size();

vector<vector<int>> g(n * 3, vector<int>(n * 3));

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

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

if (grid[i][j] == '/') {

g[i * 3 + 0][j * 3 + 2] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 0] = 1;

} else if (grid[i][j] == '\\') {

g[i * 3 + 0][j * 3 + 0] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 2] = 1;

}

int ans = 0;

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

for (int j = 0; j < 3 * n; ++j) {

if (g[i][j]) continue;

visit(g, j, i, n * 3);

++ans;

}

return ans;

}

private:

void visit(vector<vector<int>>& g, int x, int y, int n) {

if (x < 0 || x >= n || y < 0 || y >= n) return;

if (g[y][x]) return;

g[y][x] = 1;

visit(g, x + 1, y, n);

visit(g, x, y + 1, n);

visit(g, x - 1, y, n);

visit(g, x, y - 1, n);

}

};

花花酱 LeetCode 952. Largest Component Size by Common Factor

By zxi on December 1, 2018

Problem

Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

Solution: Union Find

For each number, union itself with all its factors.

E.g. 6, union(6,2), union(6,3)

Time complexity: \( O(\Sigma{sqrt(A[i])}) \)

Space complexity: \( O(max(A)) \)

C++

// Author: Huahua, running time: 148 ms

class DSU {

public:

DSU(int n): p_(n) {

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

p_[i] = i;

}

void Union(int x, int y) {

p_[Find(x)] = p_[Find(y)];

}

int Find(int x) {

if (p_[x] != x) p_[x] = Find(p_[x]);

return p_[x];

}

private:

vector<int> p_;

};

class Solution {

public:

int largestComponentSize(vector<int>& A) {

int n = *max_element(begin(A), end(A));

DSU dsu(n + 1);

for (int a : A) {

int t = sqrt(a);

for (int k = 2; k <= t; ++k)

if (a % k == 0) {

dsu.Union(a, k);

dsu.Union(a, a / k);

}

unordered_map<int, int> c;

int ans = 1;

for (int a : A)

ans = max(ans, ++c[dsu.Find(a)]);

return ans;

}

};

Python3

# Author: Huahua, running time: 3432 ms

class Solution:

def largestComponentSize(self, A):

p = list(range(max(A) + 1))

def find(x):

while p[x] != x:

p[x] = p[p[x]]

x = p[x]

return x

def union(x, y):

p[find(x)] = p[find(y)]

for a in A:

for k in range(2, int(math.sqrt(a) + 1)):

if a % k == 0:

union(a, k)

union(a, a // k)

return collections.Counter([find(a) for a in A]).most_common(1)[0][1]

Posts published in “Graph”

花花酱 LeetCode 996. Number of Squareful Arrays

Solution1: DFS

C++

Solution 2: DP Hamiltonian Path

C++

Related Problems

花花酱 LeetCode 133. Clone Graph

Solution: Queue + Hashtable

C++

花花酱 LeetCode 990. Satisfiability of Equality Equations

Solution: Union Find

C++

花花酱 LeetCode 959. Regions Cut By Slashes

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

C++

Solution 2: Euler’s Formula / Union-Find vertices

C++

Solution 3: Pixelation (Upscale 3 times)

C++

花花酱 LeetCode 952. Largest Component Size by Common Factor

Problem

Solution: Union Find

C++

Python3