# Tag: DFS

## Flood Fill Algorithm

Flood fill (also known as seed fill) is an algorithm that determines the area connected to a given node in a multi-dimensional array.

## Find all occurrences of given string in a character matrix

Given a M x N matrix of characters, find all occurrences of a given string in the matrix. We are allowed to search the string in all eight possible directions i.e. North, West, South, East, North-East, North-West, South-East, South-West. Note that there should not be any cycles in the output path.

Read More Find all occurrences of given string in a character matrix

## Check if given Graph is Strongly Connected or not

Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

Read More Check if given Graph is Strongly Connected or not

## Check if given digraph is a DAG (Directed Acyclic Graph) or not

Given an directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.   Below graph contains a cycle A-B-D-A, so it is not DAG. If we remove edge 3-0 from it, it will become a DAG.

Read More Check if given digraph is a DAG (Directed Acyclic Graph) or not

## 2-Vertex Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-vertex connected or not. A connected graph G is said to be 2-vertex-connected (or 2-connected) if it has more than 2 vertices and remains connected on removal of any vertices. Any such vertex whose removal will disconnected the graph is called Articulation point.

Read More 2-Vertex Connectivity in the graph

## 2-Edge Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-edge connected or not. A connected graph is 2-edge-connected if it remains connected whenever any edges is removed. A bridge or cut arc is an edge of a graph whose deletion increases its number of connected components. i.e. whose removal disconnects the graph. So if any such bridge exists, the graph …

Read More 2-Edge Connectivity in the graph