Cographs are a class of undirected graphs defined recursively as follows.
1. The graph with a single node is a cograph.
2. If G1, G2 are cographs with disjoint sets of nodes, then G1 ∪G2, the disjoint union of G1 and G2, is also a cograph. The set of nodes/edges in G1 ∪G2 is the union of the sets of nodes/edges in G1 and G2, respectively.
3. If G1, G2 are cographs with disjoint sets of nodes, then G1∨G2, the join of G1 and G2 is also a cograph. G1 ∨G2 is obtained from G1 ∪G2 by adding edges uv for all nodes u in G1 and v in G2. In other words, every node in G1 is joined to every node in G2.
A cograph can be represented by a labelled binary tree as follows. The single node graph is represented by the empty tree. The binary tree representing G1 ∪G2 has a root node labelled 0, with the left subtree corresponding to G1 and the right subtree corresponding to G2. Similarly, G1 ∨G2 has root node labelled 1, and left and right subtrees corresponding to G1 and G2, respectively.
Given the binary tree representation of a cograph, in the first part of the problem, you have to compute the number of edges in the graph. In the second part of the problem, you have to compute the length of the longest path in the graph.
Note that the graph is undirected and an edge is an unordered pair of nodes. The length of a path is the number of edges in it.
Submission: Submit a single file named RollNo 2.cpp .
1
