Split DAG into disjoint sets I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding and removing of components from the components list.

g = {1: [3, 4], 2: [5], 3:[7], 4:[], 5:[], 6:[1], 7:[]}

vertices = set(g)
components = []
while vertices:
  stack = list((vertices.pop(),))
  comp = set()
  while stack:
    vert = stack.pop()
    comp.add(vert)
    if vert in vertices:
       vertices.remove(vert)
    for e in g[vert]:
        if e in vertices:
            stack.append(e)
        else:
            for component in components:
               if e in component:
                  component.update(comp)
                  comp = component
                  components.remove(comp)
    components.append(comp)

print([c for c in components])


&gt;&gt;&gt; [{2, 5}, {1, 3, 4, 6, 7}]
It would seem to me that one way to solve this is to change all the directed arcs in the dag to undirected edges. The rest is to recognize the disjoint subgraphs using breadth-first search:

def convert_directed_graph_to_undirected_graph(graph):
    """Converts each directed arc into an undirected edge."""
    undirected_graph = {}
    for node, child_node_list in graph.items():
        if node not in undirected_graph.keys():
            undirected_graph[node] = []
        undirected_graph[node].extend(child_node_list)
        for child_node in child_node_list:
            if child_node not in undirected_graph.keys():
                undirected_graph[child_node] = []
            undirected_graph[child_node].append(node)
    return undirected_graph


def crawl_subgraph(source_node, undirected_graph, visited):
    """Implements breadth-first search in order to find the entire subgraph including the source noe."""
    if source_node in visited:
        return None
    visited.add(source_node)
    queue = deque([source_node])
    subgraph = [source_node]
    while queue:
        current_node = queue.popleft()
        for neighbor_node in undirected_graph[current_node]:
            if neighbor_node not in visited:
                visited.add(neighbor_node)
                subgraph.append(neighbor_node)
                queue.append(neighbor_node)
    return subgraph


def find_disjoint_dags(graph):
    """Finds all disjoint subdags in the input dag."""
    undirected_graph = convert_directed_graph_to_undirected_graph(graph)
    visited = set()
    disjoint_subgraphs = []
    vertices = set(undirected_graph)
    for vertex in vertices:
        subgraph = crawl_subgraph(vertex, undirected_graph, visited)
        if subgraph:
            disjoint_subgraphs.append(subgraph)
    return disjoint_subgraphs


Hope that helps.