Posts tagged as “connected components”

花花酱 LeetCode 841. Keys and Rooms

By zxi on May 27, 2018

Problem

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Solution: DFS

Time complexity: O(V + E)

Space complexity: O(V)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool canVisitAllRooms(vector<vector<int>>& rooms) {

unordered_set<int> visited;

dfs(rooms, 0, visited);

return visited.size() == rooms.size();

}

private:

void dfs(const vector<vector<int>>& rooms,

int cur, unordered_set<int>& visited) {

if (visited.count(cur)) return;

visited.insert(cur);

for (int nxt : rooms[cur])

dfs(rooms, nxt, visited);

}

};

花花酱 LeetCode 827. Making A Large Island

By zxi on April 30, 2018

Problem

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 1.

Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

Solution

Step 1: give each connected component a unique id and count its ara.

Step 2: for each 0 zero, check its 4 neighbours, sum areas up by unique ids.

Time complexity: O(n*m)

Space complexity: O(n*m)

C++

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

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

color_ = 1;

g_ = &grid;

m_ = grid.size();

n_ = grid[0].size();

unordered_map<int, int> areas; // color -> area

int ans = 0;

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

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

if (grid[i][j] == 1) {

++color_;

areas[color_] = getArea(j, i);

ans = max(ans, areas[color_]);

}

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

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

if (grid[i][j] == 0) {

int area = 1;

for (int color : set<int>{getColor(j, i - 1), getColor(j, i + 1),

getColor(j - 1, i), getColor(j + 1, i)})

area += areas[color];

ans = max(ans, area);

}

return ans;

}

private:

int m_;

int n_;

int color_;

vector<vector<int>>* g_; // does not own the object.

int getColor(int x, int y) {

return (x < 0 || x >= n_ || y < 0 || y >= m_) ? 0 : (*g_)[y][x];

}

// Return the area of a connected component, set all elements to color_.

int getArea(int x, int y) {

if (x < 0 || x >= n_ || y < 0 || y >= m_ || (*g_)[y][x] != 1) return 0;

(*g_)[y][x] = color_;

return 1 + getArea(x - 1, y) + getArea(x + 1, y)

+ getArea(x, y - 1) + getArea(x, y + 1);

}

};

花花酱 LeetCode 817. Linked List Components

By zxi on April 14, 2018

Problem

题目大意：给你一个链表，再给你一些合法的节点，问你链表中有多少个连通分量（所有节点必须合法）。

https://leetcode.com/problems/linked-list-components/description/

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000.
The value of each node in the linked list will be in the range [0, N - 1].
1 <= G.length <= 10000.
G is a subset of all values in the linked list.

Solution1: Graph Traversal using DFS

// Author: Huahua

// Running time: 76 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> f(G.begin(), G.end());

unordered_map<int, vector<int>> g;

int u = head->val;

while (head->next) {

head = head->next;

int v = head->val;

if (f.count(v) && f.count(u)) {

g[u].push_back(v);

g[v].push_back(u);

}

u = v;

}

int ans = 0;

unordered_set<int> visited;

for (int u : G) {

if (visited.count(u)) continue;

++ans;

dfs(u, g, visited);

}

return ans;

}

private:

void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) {

if (visited.count(cur)) return;

visited.insert(cur);

for (const int next : g[cur])

dfs(next, g, visited);

}

};

Solution 2: Count tail node in sub graph

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> g(G.begin(), G.end());

int ans = 0;

while (head) {

if (g.count(head->val) && (!head->next || !g.count(head->next->val)))

++ans;

head = head->next;

}

return ans;

}

};

花花酱 LeetCode 803. Bricks Falling When Hit

By zxi on March 18, 2018

Problem

题目大意：给你一堵砖墙，求每次击碎一块后掉落的砖头数量。

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Idea

For each day, hit and clear the specified brick.
Find all connected components (CCs) using DFS.
For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.

Solution: DFS

C++

// Author: Huahua

// Running time: 1261 ms

class Solution {

public:

vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {

dirs_ = {0, -1, 0, 1, 0};

m_ = grid.size();

n_ = grid[0].size();

g_.swap(grid);

seq_ = 1;

vector<int> ans;

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

ans.push_back(hit(hits[i][1], hits[i][0]));

return ans;

}

private:

vector<vector<int>> g_;

vector<int> dirs_;

int seq_;

int m_;

int n_;

// hit x, y and return the number of bricks fallen.

int hit(int x, int y) {

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

g_[y][x] = 0;

int ans = 0;

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

++seq_;

int count = 0;

if (!fall(x + dirs_[i], y + dirs_[i + 1], false, count)) continue;

++seq_;

ans += count;

fall(x + dirs_[i], y + dirs_[i + 1], true, count);

}

return ans;

}

// Check whether the CC contains (x, y) will fall or not.

// Set all nodes in this CC as seq_ or 0 if clear.

// count: the # of nodes in this CC.

bool fall(int x, int y, bool clear, int& count) {

if (x < 0 || x >= n_ || y < 0 || y >= m_) return true;

if (g_[y][x] == seq_ || g_[y][x] == 0) return true;

if (y == 0) return false;

g_[y][x] = clear ? 0 : seq_;

++count;

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

if (!fall(x + dirs_[i], y + dirs_[i + 1], clear, count)) return false;

return true;

}

};

Java

// Author: Huahua

// Stack Overflow (1024 recursive calls)

class Solution {

int[] dirs = new int[]{0, -1, 0, 1, 0};

int m;

int n;

int[][] g;

int seq;

int count;

public int[] hitBricks(int[][] grid, int[][] hits) {

this.g = grid;

this.m = grid.length;

this.n = grid[0].length;

int[] ans = new int[hits.length];

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

ans[i] = hit(hits[i][1], hits[i][0]);

return ans;

}

private int hit(int x, int y) {

if (x < 0 || x >= n || y < 0 || y >= m || g[y][x] == 0) return 0;

g[y][x] = 0;

int ans = 0;

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

++seq;

count = 0;

if (!fall(x + dirs[i], y + dirs[i + 1], false)) continue;

ans += count;

++seq;

fall(x + dirs[i], y + dirs[i + 1], true);

}

return ans;

}

private boolean fall(int x, int y, boolean clear) {

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

if (g[y][x] == seq || g[y][x] == 0) return true;

if (y == 0) return false;

g[y][x] = clear ? 0 : seq;

++count;

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

if (!fall(x + dirs[i], y + dirs[i + 1], clear)) return false;

return true;

}

Posts tagged as “connected components”

花花酱 LeetCode 841. Keys and Rooms

Problem

Solution: DFS

花花酱 LeetCode 827. Making A Large Island

Problem

Solution

花花酱 LeetCode 803. Bricks Falling When Hit

Problem

Idea

Solution: DFS

C++

Java

Related Problems

花花酱 LeetCode 684. Redundant Connection