Graph Cycle

Catalogue

1. 1. Detect the Cycle
   1. 1.1. 261. Graph Valid Tree
      1. 1.1.1. Solution1. Union Find
      2. 1.1.2. solution2. DFS
      3. 1.1.3. Solution3. BFS
2. 2. Directed graph
   1. 2.1. 207. Course Schedule
      1. 2.1.1. Solution1. DFS
      2. 2.1.2. Solution2. BFS
3. 3. Graph => Tree
   1. 3.1. 684. Redundant Connection
   2. 3.2. 685. Redundant Connection II

Detect the Cycle

Find if a cycle exits in a graph

261. Graph Valid Tree

• Undirected Graph: Union Find, DFS, BFS

Solution1. Union Find

• graph is represented by edges!!! signal to use union find!!!
• tree is connected graph without cycle, but graph can be seperate clusters!!!

  class Solution(object):
      def validTree(self, n, edges):
          root = range(n)
          self.cnt = n
          def find(x):
              if root[x] == x:
                  return x
              root[x] = find(root[x])
              return root[x]
  
          def union(x, y):
              rootx = find(x)
              rooty = find(y)
              if rootx != rooty:
                  root[rootx] = rooty
                  self.cnt -= 1
                  return True
              return False
  
          for i, j in edges:
              if not union(i, j):
                  return False
          return self.cnt == 1

solution2. DFS

• for undirected graph, it’s better to use Union Find and BFS
• prev node !!!!
• 3 states for visited: 0-no visited，1-visiting，2-visited

class Solution(object):
    def validTree(self, n, edges):
        graph = collections.defaultdict(set)
        for i, j in edges:
            graph[i].add(j)
            graph[j].add(i)

        visited = [0] * n
        if not self.dfs(-1, 0, visited, graph):
                return False
        return (0 not in visited)

    def dfs(self, prev, i, visited, graph):
        if visited[i] == 2:
            return True

        if visited[i] == 1:
            return False

        visited[i] = 1

        for nei in graph[i]:
            if nei == prev:
                continue
            if not self.dfs(i, nei, visited, graph):
                return False

        visited[i] = 2
        return True

Solution3. BFS

• prev node to avoid edge(a, b) and (b, a) cycle !!!

  class Solution(object):
      def validTree(self, n, edges):
          graph = collections.defaultdict(set)
          for i, j in edges:
              graph[i].add(j)
              graph[j].add(i)
  
          visited = [0] * n
          queue = collections.deque([(0, -1)])
          while queue:
              node, prev = queue.popleft()
              visited[node] = 1
              for nei in graph[node]:
                  if nei == prev:
                      continue
                  if visited[nei]:
                      return False
                  queue.append((nei, node))
          return sum(visited) == n

Directed graph

207. Course Schedule

• Directed graph: DFS, BFS

• Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

• This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

  Solution1. DFS

  visited三种状态，-1正在visit, 0未visit, 1已经visit

• Why 三种状态？or 两种状态？
  • 两种状态，做DFS时间复杂度是O(n^2)
  • 引入第三种状态，可以避免访问已经访问过不构成环的点，O(n)

# Time : O(n)
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(set)
        for c, p in prerequisites:
            graph[c].add(p)

        visited = [0] * numCourses

        for i in xrange(numCourses):
            if not self.dfs(i, visited, graph):
                return False
        return True

    def dfs(self, i, visited, graph):
        if visited[i] == 1:
            return True

        if visited[i] == -1:
            return False

        visited[i] = -1

        for edge in graph[i]:
            if not self.dfs(edge, visited, graph):
                return False

        visited[i] = 1
        return True

Solution2. BFS

• 有向图的BFS算法还是比较有意思的，基于indegree的！
• Indegree, 每次访问入度为0的节点，并删掉所在边，最后sum(indegree) == 0!

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in xrange(numCourses)]
        indegree = [0] * numCourses
        for i, j in prerequisites:
            graph[j].append(i)
            indegree[i] += 1

        queue = [i for i in xrange(numCourses) if indegree[i] == 0]
        while queue:
            course = queue.pop(0)
            for n in graph[course]:
                indegree[n] -= 1
                if indegree[n] == 0:
                    queue.append(n)
        return sum(indegree) == 0

Graph => Tree

684. Redundant Connection

• union find

  class Solution(object):
      def findRedundantConnection(self, edges):
          n = len(edges)
          root = range(n+1)
  
          def find(x):
              if root[x] == x:
                  return x
              root[x] = find(root[x])
              return root[x]
  
          for src, dst in edges:
              root1 = find(src)
              root2 = find(dst)
              if root1 != root2:
                  root[root1] = root2
              else:
                  return [src, dst]

685. Redundant Connection II

class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        candidates = []
        n = len(edges)
        parent = {}
        for i, (p, c) in enumerate(edges):
            if c in parent:
                candidates = [(parent[c], c), (p, c)]
                edges[i][0] = 0
            else:
                parent[c] = p

        # candiates is none => only cycle case
        # else => indegree > 1 case

        root = range(n+1)
        def find(x):
            if x == root[x]:
                return x
            root[x] = find(root[x])
            return root[x]

        for p, c in edges:
            root1 = find(c)
            root2 = find(p)
            if root1 == root2:
                if not candidates:
                    return [p, c]
                else:
                    return candidates[0]
            root[root1] = root2
        return candidates[1]