In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]
In this problem you should only submit a graph.h file with a self-containing definition of a class Graph.
Use as a basis the class Graph (see code | download code) which implements a graph (that can have directions and weights) using an adjacency list, assumes nodes are identified by integers between 1 and |V| and already has methods for adding an edge, reading a graph and doing a basic DFS and a basic BFS.
Add a new method int countSCCs() to the class. When called on an unweighted and directed graph, the function should return the number of strongly connected components of the graph. A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. A strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected.
All the input graphs will be simple (no self-loops or parallel edges), unweighted and directed. It is guaranteed that |V|≤100 and |E|≤500.
You should submit the file graph.h with the method countSCCs added to Graph as requested (and without removing any of the other existing methods). You can however create additional methods and/or attribute variables, if you need them.
Mooshak will use the following code to link to your class, read the inputs, build the graphs and call your method, printing its result.
#include <iostream> #include "graph.h" int main() { // Number of graphs to test int n; std::cin >> n; // For each graph: read, call the method and delete graph at the end for (int i=1; i<=n; i++) { Graph *g = Graph::readGraph(); std::cout << "Graph #" << i << ": countSCCs() = " << g->countSCCs() << std::endl; delete g; } return 0; }
Example Input | Example Output |
4 8 directed unweighted 10 1 2 2 3 4 3 5 1 2 6 7 3 3 8 8 4 6 5 8 7 8 directed unweighted 11 2 1 3 2 3 4 1 5 1 6 6 3 7 3 4 8 8 4 7 6 7 8 8 directed unweighted 12 1 2 2 3 3 4 4 3 5 1 2 5 4 8 8 4 5 6 6 7 7 6 8 7 7 directed unweighted 6 5 1 5 2 6 2 6 3 4 6 7 4 |
Graph #1: countSCCs() = 2 Graph #2: countSCCs() = 4 Graph #3: countSCCs() = 3 Graph #4: countSCCs() = 7 |
Explanation of Example Input
The first graph of the example input corresponds to the following figure:
It has 2 strongly connected components: {1,2,5,6} and {3,4,7,8}.
The second graph of the example input corresponds to the following figure:
It has 4 strongly connected components: {1,2,3,6}, {4,8}, {5} and {7}.
The third graph of the example input corresponds to the following figure:
It has 3 strongly connected components: {1,2,5}, {3,4,8} and {6,7}.
The fourth graph of the example input corresponds to the following figure:
It has 7 strongly connected components: {1}, {2}, {3}, {4}, {5}, {6} and {7}.