Posts tagged as “graph”

花花酱 LeetCode 1192. Critical Connections in a Network

By zxi on September 15, 2019

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

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.

Solution: Tarjan

Time complexity: O(v+e)
Space complexity: O(v+e)

C++

// Author: Huahua

class Solution {

public:

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

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

vector<int> ts(n, INT_MAX);

vector<vector<int>> ans;

int t = 0;

function<int(int, int)> tarjan = [&](int i, int p) {

int min_i = ts[i] = ++t;

for (int j : g[i]) {

if (ts[j] == INT_MAX) {

int min_j = tarjan(j, i);

min_i = min(min_i, min_j);

if (ts[i] < min_j)

ans.push_back({i, j});

} else if (j != p) {

min_i = min(min_i, ts[j]);

}

return min_i;

};

for (const auto& e : connections) {

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

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

}

tarjan(0, -1);

return ans;

}

};

花花酱 LeetCode 1184. Distance Between Bus Stops

By zxi on September 7, 2019

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Solution: Summation

compute the total sum
compute the sum from s to d, c
ans = min(c, sum – c)

Time complexity: O(d-s)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int distanceBetweenBusStops(vector<int>& ds, int s, int d) {

if (s > d) swap(s, d);

int sum = accumulate(begin(ds), end(ds), 0);

int d1 = accumulate(begin(ds) + s, begin(ds) + d, 0);

return min(d1, sum - d1);

}

};

花花酱 LeetCode 1162. As Far from Land as Possible

By zxi on August 17, 2019

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1)is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: BFS

Put all land cells into a queue as source nodes and BFS for water cells, the last expanded one will be the farthest.

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

C++

// Author: Huahua, 48 ms, 13.4 MB

class Solution {

public:

int maxDistance(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

int ans = -1;

queue<int> q; // y*100 + x

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

for (int j = 0; j < m; ++j)

if (grid[i][j] == 1) q.push(i * 100 + j);

vector<int> dirs{0, -1, 0, 1, 0};

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int x = p % 100;

int y = p / 100;

if (grid[y][x] == 2)

ans = max(ans, steps);

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || tx >= m || ty < 0 || ty >= n || grid[ty][tx] != 0) continue;

grid[ty][tx] = 2;

q.push(ty * 100 + tx);

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 1129. Shortest Path with Alternating Colors

By zxi on July 20, 2019

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Solution: BFS

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

C++

class Solution {

public:

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {

vector<unordered_set<int>> edges_r(n);

vector<unordered_set<int>> edges_b(n);

for (const auto& e : red_edges)

edges_r[e[0]].insert(e[1]);

for (const auto& e : blue_edges)

edges_b[e[0]].insert(e[1]);

unordered_set<int> seen_r;

unordered_set<int> seen_b;

vector<int> ans(n, -1);

queue<pair<int, int>> q; // (node, color)

q.push({0, 0}); // red

q.push({0, 1}); // blue

seen_r.insert(0);

seen_b.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int p = q.front().first;

int is_red = q.front().second;

q.pop();

ans[p] = ans[p] >= 0 ? min(ans[p], steps) : steps;

const auto& edges = is_red ? edges_r : edges_b;

auto& seen = is_red ? seen_r : seen_b;

for (int nxt : edges[p]) {

if (seen.count(nxt)) continue;

seen.insert(nxt);

q.push({nxt, 1 - is_red});

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 1042. Flower Planting With No Adjacent

By zxi on May 14, 2019

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

Solution: Graph coloring, choose any available color

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

C++

class Solution {

public:

vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {

vector<int> ans(N, 0);

vector<vector<int>> G(N);

for (const auto& p : paths) {

G[p[0] - 1].push_back(p[1] - 1);

G[p[1] - 1].push_back(p[0] - 1);

}

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

int mask = 0;

for (const auto& j : G[i])

mask |= (1 << ans[j]);

for (int c = 1; c <= 4 && ans[i] == 0; ++c)

if (!(mask & (1 << c))) ans[i] = c;

}

return ans;

}

};