Description
Write a program that receives a graph as input and determines the connectivity
of the graph and the number of the connected components in it (the graph is
undirected).
Figure 1 A disconnected graph with three components
A graph is connected when there is a path between every pair of vertices. A graph
G is said to be disconnected if there exist at least two nodes in G such that no
path in G has those nodes as endpoints. A connected component (or just
component) of a graph is a sub graph in which any two vertices are connected
to each other by paths, and which is connected to no additional vertices in the
super graph.
Input:
The first two lines of input determines number of vertices n and number of edges
m, respectively in the graph. The following m lines determine the connections in
the graph.
Output:
Output will be in one line containing 2 integers separated by a space in between.
The first integer is 0 or 1 (if the graph is disconnected then 0 otherwise 1). The
second integer is the number of disconnected components in the graph.
SR Input Output
1
9
9
1 2
2 3
3 4
2 4
1 3
2 8
5 7
6 7
5 6
0 3