« back

Articulation Point - II

Tags : graph, geeksforgeeks, cpp, hard

Problem Statement - link #

Given an undirected connected graph (not necessarily connected) with V vertices and adjacency list adj. You are required to find all the vertices removing which (and edges through it) disconnects the graph into 2 or more components. Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops present in the graph.

Your Task: You don’t need to read or print anything. Your task is to complete the function articulationPoints() which takes V and adj as input parameters and returns a list containing all the vertices removing which turn the graph into two or more disconnected components in sorted order. If there are no such vertices then returns a list containing -1.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:


Output:{1,4}
Explanation: Removing the vertex 1 will
discconect the graph as-


Removing the vertex 4 will disconnect the
graph as-

Constraints #

Solutions #

class Solution
{
	public:
    void APUtil(int u, vector<int>adj[], bool vis[], int dis[], int low[], int parent[],set<int>&ap) { 
    	static int time = 0; 
    	int children = 0; 
    	vis[u] = true; 
    	dis[u] = low[u] = ++time; 
    	for (int v: adj[u])	{ 
    		if (!vis[v]) 		{ 
    			children++; 
    			parent[v] = u; 
    			APUtil(v, adj, vis, dis, low, parent, ap); 
    			low[u] = min(low[u], low[v]); 
    			if (parent[u] == -1 && children > 1) 
    			ap.insert(u);
    			if (parent[u] != -1 && low[v] >= dis[u]) 
    			ap.insert(u);
    		} 
    		else if (v != parent[u]) 
    			low[u] = min(low[u], dis[v]); 
    	} 
    } 
    vector<int> articulationPoints(int V, vector<int>adj[]) {
        // Code here
    	bool *vis = new bool[V]; 
    	int *dis = new int[V]; 
    	int *low = new int[V]; 
    	int *parent = new int[V]; 
    	set<int> ap; 
    	
    	for (int i = 0; i < V; i++) 
    	{ 
    		parent[i] = -1; 
    		vis[i] = false; 
    	} 
    	
    	for (int i = 0; i < V; i++) 
    		if (vis[i] == false) 
    			APUtil(i,adj, vis, dis, low, parent, ap); 
        vector<int> res;
        if(ap.size()){
            for(auto it: ap)
                res.push_back(it);
        }else res.push_back(-1);
    	return res;
    }
};