div1's blog

A Graph Problem
By div1, 11 years ago, In English

there is a graph of at most 10000 vertices and 100000 edges. all the vertices of the graph may not be connected. how to find the the different component sizes if we remove an articulation point from the graph. We have to do this for all the articulation points.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't quite understand the problem statement.

  • Is the graph directed or undirected?
  • What do you mean by "picking" an articulation point?

I suppose you mean removing an articulation point, thus dividing a component into two or more components, and finding the sizes of those new components?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    i think so

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The Graph is undirected. "I suppose you mean removing an articulation point, thus dividing a component into two or more components, and finding the sizes of those new components?" YES thats it.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      I think you can find all biconnected components and store for each articulation node a list containing sizes of all components that including that node.

      Edit: Sorry, I've just realized that it doesn't work in case one component has 2 or more articulation nodes. Yet I still think we can modify that algorithm a bit to make it work by adding a counter when performing DFS.

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

To find articulation points, you can do a DFS. The algorithm is as follows...

1) Do a DFS starting from an arbitrary node (say node 1)

2) Number the nodes as you visit them with DFS (Num[i])

3) Let Low[i] be the least numbered node in the DFS subtree rooted at i or connected to a node in that subtree by a back edge

Then, if L[i] >= Num[i], the node is an articulation point.

Finally, what I'd do, since there are at most 10^4 vertices, for every articulation point, do a DFS and recalculate the size of the components (DFS takes N steps to complete), so the overall complexity of the algorithm is O(N^2), which is fairly reasonable for N = 10^4.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This must be calculated in O(n).

    → Reply
»
11 years ago, # |
← Rev. 8   Vote: I like it +1 Vote: I do not like it

In fact, you don't even need to do a DFS everytime you remove an articulation point. In the first DFS you do to identify articulation points, you can keep a list subsizes[i], which stores the sizes of the sub-components you would get when you remove node i. The way to do that is...

  • You have a variable dfsNum, which keeps the number of nodes visited so far by the DFS
  • When you recursively call DFS(k), with k being a child of i, you make prevNum = dfsNum (you keep track of the number of nodes visited before entering node k), and when the function returns, the size of the sub-component will be dfsNum — prevNum. That is, the size of that branch of the DFS subtree rooted at i.

The pseudo-code for that part would be something like this...

DFS(n, &dfsNum)
{
    minTouch = dfsNum
    Num[n] = dfsNum

    for(every child k of n)
    {
        if(!visited(n))
        {
            prevNum = dfsNum
            first = DFS(k, dfsNum + 1)
            if(first > Num[n])
                subsizes[n].push_back(dfsNum - prevNum)
        }
        
        minTouch = min(first, Num[k])
    }
    
    return minTouch;
}

Then, when you remove the articulation point n, you just print the sizes of the original components (except the component that contains node n), the data stored at subsizes[n] and the size of the original component that contained node n minus the sum of all the elements in subsizes[n] minus 1.

I think that should work, hopefully I'm not forgetting to consider something... maybe someone can help me around :)

EDIT: Yes, actually I was forgetting something. Since the graph is not a tree, one of children branches of node n can connect with the parent's branch, so we also need to keep track of 'first', the least numbered node that the branch touches. If first < Num[n], then we don't consider that branch as a subcomponent. I changed the code. I'm still quite not sure it'd work...

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    i still dont get it. can you please give a complete code ... thanks

    → Reply