I have a strongly connected graph. I want to remove an edge and check if still remains strongly connected. As i'm taking N = Total number of nodes in the graph to be 10 and most of the graphs that i'm interested in has above 25 edges its hard to check using one at a time removing edge.
How to solve this problem ? Thanks.
If the edge you remove is (u -> v), the graph will remain connected if you can find a path from u to v. You can use any path finding algorithm to check this.
Another option is to run a connectivity check algorithm from scratch every time; it doesn't really matter how you do this because the graph is very small.
For a larger graph, there are special data structures that have been designed for this problem. It's called "Dynamic connectivity": https://en.wikipedia.org/wiki/Dynamic_connectivity
[EDIT: DFS is faster than Dijkstra for just checking connectivity, thanks to Jørgen Fogh]
If the edge you're removing is uv, check (e.g. using DFS) whether there remains a path u->...->v. If so, the graph is still strongly connected if it was before. If not, then it's clearly no longer strongly connected.
The idea is that any path between two vertices x and y that previously used the edge uv can be edited to use the new path u->...->v. Simply replacing the edge uv with this new path might cause some vertices to be visited more than once -- but in this case, the path contains one or more directed cycles which can be removed, until the remaining path visits each vertex at most once.
