Articulation Point.

Image result for articulation point

In graph theory, articulation point is a vertex upon its removal disconnects the graph into two components. Articulation point is very important in communication networks since it tell which all nodes upon damage will cause failure to network.

Modified DFS can be used to efficiently find the articulation point in the graphs. The idea is very simple.

  1. We start with one node as root.Run the DFS on the root node.
  2. For each node maintain two time values.
    • DiscoveryTime- Time in which the node was first reached.
    • Low Time- Low Time of a node is the lowest discovery time of all of its adjacent nodes
  3. A node is an articulation point if it satisfy any of the following properties.
    • If node is root node and node has two children.
    • If node's low time is lower than the low time of all other adjacent nodes

Lets start coding:

Lets create two functions for finding articulation point  Ap() and ApUtil();

Ap() is used to initialize all the structures we need and ApUtil() does the real work. We will write it as recursive functions.


void Ap(vector<int> adj[],int src,int V)
{
    vector<int> parent(V,-1);
    vector<int> ap(V,false);
    vector<int> visited(V,false);
    vector<int> disc;
    vector<int> low;

    APUtil(adj,src,visited,parent,ap,low,disc); //Here we call the APUtil() with root node as src

}

APUtil() function is used to carry out the actual work of finding the articulation point


void APUtil(vector<int> adj[],int src,vector<int> visited,vector<int>parent,vector<int> ap,vector<int>low,vector<int>disc)
{
    visited[src]=true;

    static int time =0;

    int children=0;

    disc[src]=time+1;

    low[src]=time+1;

    time=time+1;
    int u=src;

    for(auto i=adj[u].begin();i!=adj[u].end();i++)
    {

        int v=(*i);

        if(visited[v]==false)  {
               children++;
               parent[v]=u;
               APUtil(adj,v,visited,parent,ap,low,disc); 

               low[u]=min(low[u],low[v]);

               //conditions to check for the articulation points

               if(parent[u]==-1 && children>1)
                             ap[u]==true;

               if ( parent[u]!=-1 && disc[u]<=low[v])
                             ap[u]=true;

                               }
         else if(v!=parent[u])
               {

                  low[u]=min(low[u],disc[v]);
               }

     }

}

Complete code:

#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define INF 1000000

void addEdge(vector<int>adj[],int u,int v)
{
	adj[u].pb(v);
}	

void APUtil(int u,vector<bool> visited,vector<int> disc,vector<int> parent, vector<bool>ap,vector<int> adj,int V)
{
	static int time=0;

	int children=0;

	visited[u]=true;

	disc[u]=low[u]=++time;

	for(auto i=adj[u].begin();i!=adj[u].end();i++)
	{
		int v=(*i);

		if(!visited[v])
		{
			children++;

			parent[v]=u;
			APUtil(v,visited,disc,parent,ap,

			 low[u]  = min(low[u], low[v]);

            if (parent[u] == NIL && children > 1)
               ap[u] = true;

            if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;
		}

		 else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);

	}

}

void ap(vector<int> adj[],int s,int V)
{
	vector<bool> ap;
	vector<int> parent(V,-1);
	vector<int> low;
	vector<int> disc(V,0);
	vector<bool> visited(V,false);

	for(int i=0;i<V;i++) 		if(!visited[i]) 			APUtil(i,visited,disc,parent,ap,adj,V); 	 	 } int main() { 	int V; 	cin>>V;

	vector<int> adj[V];

	return 0;
}

Reference : https://www.youtube.com/watch?v=2kREIkF9UAs

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s