Posts published in “Graph”

花花酱 LeetCode 684. Redundant Connection

By zxi on September 28, 2017

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:

Input: [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The given undirected graph will be like this:

/ \

2 - 3

Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4]

Explanation: The given undirected graph will be like this:

5 - 1 - 2

| |

4 - 3

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

// Author: Huahua

// Time Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

unordered_map<int, vector<int>> graph;

for (const auto& edge : edges) {

int u = edge[0];

int v = edge[1];

unordered_set<int> visited;

if (hasPath(u, v, graph, visited))

return edge;

graph[u].push_back(v);

graph[v].push_back(u);

}

return {};

}

private:

bool hasPath(int curr,

int goal,

const unordered_map<int, vector<int>>& graph,

unordered_set<int>& visited) {

if (curr == goal) return true;

visited.insert(curr);

if (!graph.count(curr) || !graph.count(goal)) return false;

for (int next : graph.at(curr)) {

if (visited.count(next)) continue;

if (hasPath(next, goal, graph, visited)) return true;

}

return false;

}

};

C++ / Union Find

// Author: Huahua

// Running time: 6 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

ranks_ = vector<int>(n + 1, 0);

parents_ = vector<int>(n + 1, 0);

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

parents_[i] = i;

}

// Merge sets that contains u and v.

// Return true if merged, false if u and v are already in one set.

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

// Meger low rank tree into high rank tree

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pv] += 1;

}

return true;

}

// Get the root of u.

int Find(int u) {

// Compress the path during traversal

if (u != parents_[u])

parents_[u] = Find(parents_[u]);

return parents_[u];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

UnionFindSet s(edges.size());

for(const auto& edge: edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return {};

}

};

Java / Union Find

// Author: Huahua

// Runtime: 6 ms

class Solution {

class UnionFindSet {

private int[] parents_;

private int[] ranks_;

public UnionFindSet(int n) {

parents_ = new int[n + 1];

ranks_ = new int[n + 1];

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

parents_[i] = i;

ranks_[i] = 1;

}

public boolean Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

public int Find(int u) {

while (parents_[u] != u) {

parents_[u] = parents_[parents_[u]];

u = parents_[u];

}

return u;

}

public int[] findRedundantConnection(int[][] edges) {

UnionFindSet s = new UnionFindSet(edges.length);

for (int[] edge : edges)

if (!s.Union(edge[0], edge[1]))

return edge;

return null;

}

Python: Union Find

"""

Author: Huahua

Running Time: 66 ms

"""

class Solution:

def findRedundantConnection(self, edges):

p = [0]*(len(edges) + 1)

s = [1]*(len(edges) + 1)

def find(u):

while p[u] != u:

p[u] = p[p[u]]

u = p[u]

return u

for u, v in edges:

if p[u] == 0: p[u] = u

if p[v] == 0: p[v] = v

pu, pv = find(u), find(v)

if pu == pv: return [u, v]

if s[pv] > s[pu]: u, v = v, u

p[pv] = pu

s[pu] += s[pv]

return []

Python / Union Find V2

"""

Author: Huahua

Runtime: 59 ms (<92.42%)

"""

class UnionFindSet:

def __init__(self, n):

self._parents = [i for i in range(n + 1)]

self._ranks = [1 for i in range(n + 1)]

def find(self, u):

while u != self._parents[u]:

self._parents[u] = self._parents[self._parents[u]]

u = self._parents[u]

return u

def union(self, u, v):

pu, pv = self.find(u), self.find(v)

if pu == pv: return False

if self._ranks[pu] < self._ranks[pv]:

self._parents[pu] = pv

elif self._ranks[pu] > self._ranks[pv]:

self._parents[pv] = pu

else:

self._parents[pv] = pu

self._ranks[pu] += 1

return True

class Solution:

def findRedundantConnection(self, edges):

s = UnionFindSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

ndSet(len(edges))

for edge in edges:

if not s.union(edge[0], edge[1]): return edge

return None

花花酱 LeetCode 547. Friend Circles

By zxi on September 21, 2017

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 i_thand j_th 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:

Input:

[[1,1,0],

[1,1,0],

[0,0,1]]

Output: 2

Example 2:

Input:

[[1,1,0],

[1,1,1],

[0,1,1]]

Output: 1

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

Idea:

Find all connected components using DFS

Solution: DFS

C++

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 25 ms

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

if (M.empty()) return 0;

int n = M.size();

int ans = 0;

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

if (!M[i][i]) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private:

void dfs(vector<vector<int>>& M, int curr, int n) {

// Visit all friends (neighbors)

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

if (!M[curr][i]) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

};

Java

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 20 ms

class Solution {

public int findCircleNum(int[][] M) {

int n = M.length;

if (n == 0) return 0;

int ans = 0;

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

if (M[i][i] == 0) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private void dfs(int[][] M, int curr, int n) {

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

if (M[curr][i] == 0) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

Python

"""

Author: Huahua

Time complexity: O(n^2)

Space complexity: O(n)

Running Time: 162 ms

"""

class Solution(object):

def findCircleNum(self, M):

"""

:type M: List[List[int]]

:rtype: int

"""

def dfs(M, curr, n):

for i in xrange(n):

if M[curr][i] == 1:

M[curr][i] = M[i][curr] = 0

dfs(M, i, n)

n = len(M)

ans = 0

for i in xrange(n):

if M[i][i] == 1:

ans += 1

dfs(M, i, n)

return ans

Solution 2: Union Find

C++

// Author: Huahua

// Runtime: 19 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

parents_ = vector<int>(n + 1, 0);

ranks_ = vector<int>(n + 1, 0);

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

parents_[i] = i;

}

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pu] > ranks_[pv]) {

parents_[pv] = pu;

} else if (ranks_[pv] > ranks_[pu]) {

parents_[pu] = pv;

} else {

parents_[pu] = pv;

++ranks_[pv];

}

return true;

}

int Find(int id) {

if (id != parents_[id])

parents_[id] = Find(parents_[id]);

return parents_[id];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

int n = M.size();

UnionFindSet s(n);

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

for (int j = i + 1; j < n; ++j)

if (M[i][j] == 1) s.Union(i, j);

unordered_set<int> circles;

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

circles.insert(s.Find(i));

return circles.size();

}

};

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

// Author: Huahua

// Time complexity: O(mn)

// Running time: 6 ms

class Solution {

public:

int numIslands(vector<vector<char>>& grid) {

if (grid.empty()) return 0;

int m = grid.size();

int n = grid[0].size();

int ans = 0;

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

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

ans += grid[y][x] - '0';

dfs(grid, x, y, m, n);

}

return ans;

}

private:

void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, m, n);

dfs(grid, x - 1, y, m, n);

dfs(grid, x, y + 1, m, n);

dfs(grid, x, y - 1, m, n);

}

};

Java

// Author: Huahua

// Time Complexity: O(mn)

// Running time: 13 ms

class Solution {

public int numIslands(char[][] grid) {

int m = grid.length;

if (m == 0) return 0;

int n = grid[0].length;

int ans = 0;

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

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

if (grid[y][x] == '1') {

++ans;

dfs(grid, x, y, n, m);

}

return ans;

}

private void dfs(char[][] grid, int x, int y, int n, int m) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, n, m);

dfs(grid, x - 1, y, n, m);

dfs(grid, x, y + 1, n, m);

dfs(grid, x, y - 1, n, m);

}

Python

"""

Author: Huahua

Time Complexity: O(mn)

Running Time: 102 ms

"""

class Solution(object):

def numIslands(self, grid):

"""

:type grid: List[List[str]]

:rtype: int

"""

m = len(grid)

if m == 0: return 0

n = len(grid[0])

ans = 0

for y in xrange(m):

for x in xrange(n):

if grid[y][x] == '1':

ans += 1

self.__dfs(grid, x, y, n, m)

return ans

def __dfs(self, grid, x, y, n, m):

if x < 0 or y < 0 or x >=n or y >= m or grid[y][x] == '0':

return

grid[y][x] = '0'

self.__dfs(grid, x + 1, y, n, m)

self.__dfs(grid, x - 1, y, n, m)

self.__dfs(grid, x, y + 1, n, m)

self.__dfs(grid, x, y - 1, n, m)

Posts published in “Graph”

花花酱 LeetCode 684. Redundant Connection

花花酱 LeetCode 547. Friend Circles

Solution: DFS

C++

Java

Python

Solution 2: Union Find

C++

Related Problems

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 675. Cut Off Trees for Golf Event

花花酱 LeetCode 332. Reconstruct Itinerary