CareerCup

I think making a n-ary tree should work. Start by any node and Do BFS. If you encounter any node that already in the tree except its parent, that means that node is not critical.

I think we can remove each node from the graph(one at a time) and check if the graph is still connected(doing BFS or DFS) and then add the node back to the graph.
I am sure there must be a more optimal solution for this.

Remove each node from the graph(one at a time) and then check if the graph is still connected(By doing BFS or DFS) and add the node back to the graph.
I am sure there exists a more optimal solution to this.

Remove each node from the graph(one vertex at a time) and then check if the graph is still connected(By doing DFS or BFS) and then add the node back to the graph.
I am sure there exists a more optimal solution to this.

manish i think the question is not clear.Each one interpreting the question in similar way. can you explain me in person :)

We can use BFS with path length property, if any node has length 3 from source than source and this node are critical nodes.
Incase of A-C-B & A-D-E-B, A-D-E will be critical path.

private int[] bfs(char s){
		boolean[] visited = new boolean[26];
		int[] count = new int[26];
		Queue<Character> q = new LinkedList<Character>();
		q.offer(s);
		visited[s - 'A'] = true;
		count[s -'A'] = 1;
		while(! q.isEmpty()){
			char tmp = q.poll();
			for(char x : getAdjacentVertices(tmp)){
				int indics = x - 'A';
				if(! visited[indics]){
					q.offer(x);
					visited[x - 'A'] = true;
					count[indics] = count[ tmp - 'A'] + 1;
				} else{
					count[indics] = count[ tmp - 'A'] + 1;
				}
			}
		}
		return count;
	}
	public List<Character> findCriticalNodes(){
		int[] count =  bfs(source);
		LinkedList<Character> nodes = new LinkedList<Character>();
		for(int x = 0 ; x < 26; x++){
			if(count[x] == 3){
				nodes.add((char) (x  + 'A'));
			}
		}
		if(! nodes.isEmpty()){
			nodes.addFirst(source);
		}
		return nodes;
	}

Time Complexity O(V(V+E)) here, V is # of vertex and E is # edges

For a given vertex V,

- Maintain list of its immediate neighbor (i.e. pathlength 1). Call it as SINGLE_HOP
- Maintain list of immediate neighbors of SINGLE_HOP list, call it as ANSWER.
- ANSWER is the superset of our what our final answer will be.
- Now run BFS on V as root, remove all elements from ANSWER which can be reached using BFS with pathlength more than 2.
- If BFS finds a path with pathlength > 1 for an element in SINGLE_HOP, then remove all its immediate neighbors from ANSWER. store/append ANSWER => FINAL_ANSWER
- Repeat above with each edge.

FINAL_ANSWER contains final answer

I am interpreting this question as finding all critical paths, each defined by a pair of critical nodes.

For single-source critical path from source n:
- Do BFS where the limit of the search is of distance 2
- Track nodes of distance 1 from n
- When searching nodes of distance 2 from n, if it does not also exist at distance 1 from n (tracked in previous step), then add it to result set
- Result set now contains all nodes that form a critical path with n

For all sources critical paths:
- Easy solution is to just repeat the single-source solution for all nodes.

typedef pair<int, int> Node;

vector<int> *G; bool *onStack, *judge, *visited; int V;

void dfs(int u, int p, int d)
{
	visited[u] = true; onStack[u] = true; if (d != 2) judge[u] = false;

	++d;

	for (int v : G[u])
	{
		if (v != p && !onStack[v]) dfs(v, u, d);
	}

	onStack[u] = false;
}

vector<Node> findCriticalNodes(vector<int> G[], int V)
{
	::G = G; ::V = V;

	onStack = new bool[V]; judge = new bool[V]; visited = new bool[V];

	vector<Node> ans;

	for (int u = 0; u < V - 1; ++u)
	{
		memset(onStack, false, V); memset(judge, true, V); memset(visited, false, V);

		dfs(u, -1, 0);

		for (int v = 0; v < V; ++v)
		{
			if (visited[v] && judge[v]) ans.push_back(Node(u, v));
		}
	}

	return move(ans);
}

1) run all nodes shortest path algorithm
2) all the nodes whose paths size is greater than 2 are not ciritical
3) now find logest path between nodes by negating all the edge weights
4) if longest paths are greater than 2 then we can eliminate pairs form 2

Articulation Points in a Graph