Delete leaves layer by layer,without modifying the graph


  • 0
    H

    I saw many codes based on this idea use adjacency list to represent the graph,and when delete leaves,they delete the elementary in adjacency list indeed.It is obvious that delete operation of set data structure cost O(log(n)) time,so the time complexity should be close to O(nlog(n)) rather than O(n).
    There is one way we can achieve the same target on O(n) time cost,without change the graph.
    Let's add a new vector representing whether the node is delete as an leave.When we delete a leave whose id is i,we traversal the neighbors of i (in adj[i]) and check whether it(neighbor) is deleted.If not ,we decrease the degree of the neighbor.Then we marked node i as deleted.

    Let's look at the time complexity:
    every node is deleted once and when deleted,its neighbor is visited once,which means we visited all edges once. So the total time for this two operation is O(n)+O(n-1)=O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.