亚麻新出炉的OA难题 - 没人做得来

Job Hunting Interview
, , , , ,
1

亚麻今天有道题，类似这道题 https://www.geeksforgeeks.org/bridge-in-a-graph/
几个同学一起做没做出来

image

里面的第二个

2

所以这题和geekforgeeks这道题区别在于？

3

这题其实就是找到circle，circle里的edge可以删
参考 https://leetcode.com/problems/find-eventual-safe-states/

eventual-safe-states的node都是circle之外的

5
6

thanks! good idea

7

Given an underected graph with n nodes labeled 1..n . A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all bridges in the given graph. Output an empty list if there are no bridges.

Input:

  • n , an int representing the total number of nodes.
  • edges , a list of pairs of integers representing the nodes connected by an edge.

Example 1:

Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]

image

Output: [[1, 2], [4, 5]]
Explanation:
There are 2 bridges:

  1. Between node 1 and 2
  2. Between node 4 and 5
    If we remove these edges, then the graph will be disconnected.
    If we remove any of the remaining edges, the graph will remain connected.

Example 2:

Input: n = 6, edges = [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [4, 6], [5, 6]]

image

Output: []
Explanation:
We can remove any edge, the graph will remain connected.

8 
A---B---C---D
|   |   |   |
E---F   G---H

这个edge case B—C你的算法识别不出来

9

嗯，看来必须是同一个cycle的才行

10
11

找cycle用union find可以么？感觉挺快的