393. Count number of subgraphs in a given graph

Objective: Given a Graph, write a program to count all the subgraphs.

Example:

Approach: Use Depth-First Search

Start the DFS from any random vertex. Once DFS is completed check if all the vertices are visited. If the graph is completed connected then after first DFS all the vertices will be marked as visited. If the graph is disconnected then start another DFS from any vertex which is still not visited after the first round of DFS and check again if all the vertices are visited. Repeat the above process until all the vertices are visited. Keep counting the no of DFS calls. This will be our answer to the number of subgraphs.

Output:

Number of Subgraphs: 4
Number of Subgraphs: 3
Number of Subgraphs: 2
Number of Subgraphs: 1

Related Problems:

- Graph – Software Installation Problem Medium
- Graph – Find Number of non reachable vertices from a given vertex Medium
- Graph – Depth First Search using Recursion Beginner
- Graph – Print all paths between source and destination Medium
- Max Flow Problem – Introduction Hard