For the complexity analysis, drive the worst-case time complexity. Try not to give upper bounds which are too loose. If possible, try to give a tight upper bound by using .

#include

#include

#include

#include

#include

#include

using namespace std;

typedef int Vertex;

typedef unordered_map<int, vector<int>> AdjacencyList;

Vertex decide_root(AdjacencyList& graph);

void LSC(AdjacencyList& graph, Vertex root);

void LSC_TRAV(AdjacencyList& graph, Vertex root, Vertex u);

Vertex get_leaf();

void join_leaf_node(Vertex root, Vertex leaf);

void PRINT_CYCLE(AdjacencyList& graph, Vertex root, Vertex v);

AdjacencyList randomGraphGenerator(int vertex);

int counter = 0; // count (name for the variable) has a name confict with a fucntion, use counter

unordered_map colors;

unordered_map pred;

unordered_map path;

unordered_mapint> discover;

unordered_mapint> finish;

int main()

{

auto begin = std::chrono::high_resolution_clock::now();

srand((unsigned) time(0));

AdjacencyList G;

/*

G[1] = { 2, 5 };

G[2] = { 1, 3, 5 };

G[3] = { 1, 2, 4, 5 };

G[4] = { 3, 5 };

G[5] = { 2, 3, 4 };

*/

G = randomGraphGenerator(20);

int n = 10000;

for(int i=0; i

{

G = randomGraphGenerator(20);

Vertex root = decide_root(G);

LSC(G, root);

Vertex leaf = get_leaf(); // Incomplete

join_leaf_node(root, leaf);

PRINT_CYCLE(G, root, leaf);

cout << root << endl; // print root, again, to indicate a cycle

}

//Vertex root = decide_root(G);

//LSC(G, root);

//Vertex leaf = get_leaf(); // Incomplete

//join_leaf_node(root, leaf);

//PRINT_CYCLE(G, root, leaf);

//cout << root << endl; // print root, again, to indicate a cycle

auto end = std::chrono::high_resolution_clock::now();

auto elapsed = std::chrono::duration_cast(end - begin);

printf("Time measured: %.3f seconds. ", elapsed.count() * 1e-9);

return 0;

}

Vertex decide_root(AdjacencyList& graph)

{

size_t max = 0;

Vertex max_v = 0;

for (auto item : graph)

{

if (item.second.size() >= max)

{

max_v = item.first;

max = item.second.size();

}

}

return max_v;

}

void LSC(AdjacencyList& graph, Vertex root)

{

for (auto item : graph)

{

Vertex u = item.first;

if (u == root) continue;

colors[u] = "white";

path[u] = 0;

pred[u] = 0;

}

counter = 0;

for (Vertex u : graph[root])

{

if (colors[u] == "white") LSC_TRAV(graph, root, u);

}

}

void LSC_TRAV(AdjacencyList& graph, Vertex root, Vertex u)

{

colors[u] = "pink";

counter += 1;

discover[u] = counter;

for (Vertex v : graph[u])

{

if (v == root) finish[u] = counter + 1;

else if (graph[u].size() == 0) finish[u] = counter;

else if (colors[v] == "white")

{

pred[v] = u;

path[u] = v; // use this hash map to determine the leaf node

LSC_TRAV(graph, root, v);

}

}

colors[u] = "red";

counter += 1;

finish[u] = counter;

}

Vertex get_leaf()

{

for (auto item : path)

{

if (item.second == 0) return item.first;

}

return 0;

}

void join_leaf_node(Vertex root, Vertex leaf)

{

for (auto item : pred)

{

if (item.second == 0) pred[item.first] = root;

}

pred[root] = leaf;

}

void PRINT_CYCLE(AdjacencyList& graph, Vertex root, Vertex v)

{

if (v == root) cout << root << " ";

else if (pred[v] == 0) cout << "no cycle exists";

else

{

PRINT_CYCLE(graph, root, pred[v]);

cout << v << " ";

}

}

AdjacencyList randomGraphGenerator(int vertex){

AdjacencyList list;

for (int i = 1; i < vertex; i++){

int x = rand() % 8 + 1;

int randomEdgeCount = rand() % vertex + x;

for(int k = 0; k < randomEdgeCount; k++){

int randomVertex = rand() % vertex + 1;

list[i].push_back(randomVertex);

}

}

return list;

}