Press "Enter" to skip to content

Posts published in “Graph”

花花酱 LeetCode 695. Max Area of Island

Problem:

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.



Idea:

Use DFS to find the connected components

Solution:

C++

 

Related problems:

花花酱 LeetCode 685. Redundant Connection II

Problem:

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Example 2:

Note:

 

  • The size of the input 2D-array will be between 3 and 1000.
  • Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.



Idea:

Union Find

Time complexity: O(nlog*n) ~ O(n)

Space complexity: O(n)

Solution:

C++

 

C++ / without using Union find

 

Python

 

花花酱 LeetCode 684. Redundant Connection

https://leetcode.com/problems/redundant-connection/description/

Problem:

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Example 2:

Note:

 

  • The size of the input 2D-array will be between 3 and 1000.
  • Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.



Idea:
DFS / Union-Find

 

Solutions:

C++ / DFS

 

C++ / Union Find

Java / Union Find

 

Python: Union Find

Python / Union Find V2

 

 

花花酱 LeetCode 547. Friend Circles

Problem:

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ithand jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Example 2:

  1. N is in range [1,200].
  2. M[i][i] = 1 for all students.
  3. If M[i][j] = 1, then M[j][i] = 1.

Idea:

Find all connected components using DFS



Solution: DFS

C++

Java

Python

Solution 2: Union Find

C++

 

Related Problems

花花酱 LeetCode 200. Number of Islands

Problem:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

Solution

C++

Java

Python

Related Problems