snippets/graph/Connectivity/biconnected.cpp
bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])
{
    // A static variable is used for simplicity, we can avoid use of static
    // variable by passing a pointer.
    static int time = 0;

    // Count of children in DFS Tree
    int children = 0;

    // Mark the current node as visited
    visited[u] = true;

    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;

    // Go through all vertices aadjacent to this
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;  // v is current adjacent of u

        // If v is not visited yet, then make it a child of u
        // in DFS tree and recur for it
        if (!visited[v])
        {
            children++;
            parent[v] = u;

            // check if subgraph rooted with v has an articulation point
            if (isBCUtil(v, visited, disc, low, parent))
               return true;

            // Check if the subtree rooted with v has a connection to
            // one of the ancestors of u
            low[u]  = min(low[u], low[v]);

            // u is an articulation point in following cases

            // (1) u is root of DFS tree and has two or more chilren.
            if (parent[u] == NIL && children > 1)
               return true;

            // (2) If u is not root and low value of one of its child is
            // more than discovery value of u.
            if (parent[u] != NIL && low[v] >= disc[u])
               return true;
        }

        // Update low value of u for parent function calls.
        else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);
    }
    return false;
}
// A recursive function that returns true if there is an articulation
// point in given graph, otherwise returns false.
// This function is almost same as isAPUtil() here ( http://goo.gl/Me9Fw )
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
A recursive function that returns true if there is an articulation
point in given graph, otherwise returns false.
A recursive function that returns true if there is an articulation point in given graph otherwise returns false .
bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])
{
    static int time = 0;
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;  
        if (!visited[v])
        {
            children++;
            parent[v] = u;
            if (isBCUtil(v, visited, disc, low, parent))
               return true;
            low[u]  = min(low[u], low[v]);
            if (parent[u] == NIL && children > 1)
               return true;
            if (parent[u] != NIL && low[v] >= disc[u])
               return true;
        }
        else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);
    }
    return false;
}
bool Graph :: isBCUtil ( int u , bool visited [ ] , int disc [ ] , int low [ ] , int parent [ ] ) { static int time = 0 ; int children = 0 ; visited [ u ] = true ; disc [ u ] = low [ u ] = ++ time ; list < int > :: iterator i ; for ( i = adj [ u ] . begin ( ) ; i != adj [ u ] . end ( ) ; ++ i ) { int v = * i ; if ( ! visited [ v ] ) { children ++ ; parent [ v ] = u ; if ( isBCUtil ( v , visited , disc , low , parent ) ) return true ; low [ u ] = min ( low [ u ] , low [ v ] ) ; if ( parent [ u ] == NIL && children > 1 ) return true ; if ( parent [ u ] != NIL && low [ v ] >= disc [ u ] ) return true ; } else if ( v != parent [ u ] ) low [ u ] = min ( low [ u ] , disc [ v ] ) ; } return false ; }
A recursive function that returns true if there is an articulation
point in given graph, otherwise returns false.
A recursive function that returns true if there is an articulation point in given graph otherwise returns false .
// A static variable is used for simplicity, we can avoid use of static // variable by passing a pointer. // Count of children in DFS Tree // Mark the current node as visited // Initialize discovery time and low value // Go through all vertices aadjacent to this // v is current adjacent of u // If v is not visited yet, then make it a child of u // in DFS tree and recur for it // check if subgraph rooted with v has an articulation point // Check if the subtree rooted with v has a connection to // one of the ancestors of u // u is an articulation point in following cases // (1) u is root of DFS tree and has two or more chilren. // (2) If u is not root and low value of one of its child is // more than discovery value of u. // Update low value of u for parent function calls.