I'm trying to do some analysis on the time complexity of Kosaraju and Tarjan algorithm to find strongly connected components in a directed graph but the process of making up the graph is taking too much time. I tried making this 21 nodes graph but this too took me too long, i don't think continuing this way till 1k nodes is a good strategy.
class Graph
{
public:
int vertex;
vector<int> *adjcent_list;
Graph(int vertex){
(*this).vertex=vertex;
adjcent_list = new vector<int>[vertex];
}
void add_edge(int a, int b)
{
adjcent_list[a].push_back(b);
}
};
int main()
{
Graph g(22);
g.add_edge(0, 1);
g.add_edge(1, 2);
g.add_edge(1, 3);
g.add_edge(3, 4);
g.add_edge(4, 0);
g.add_edge(4, 5);
g.add_edge(4, 6);
g.add_edge(5, 6);
g.add_edge(6, 5);
g.add_edge(6, 7);
g.add_edge(7, 5);
g.add_edge(7, 8);
g.add_edge(8, 9);
g.add_edge(9, 11);
g.add_edge(9, 13);
g.add_edge(11, 12);
g.add_edge(12, 13);
g.add_edge(12, 9);
g.add_edge(12, 8);
g.add_edge(8, 10);
g.add_edge(10, 13);
g.add_edge(13, 14);
g.add_edge(14, 15);
g.add_edge(15, 16);
g.add_edge(16, 17);
g.add_edge(17, 18);
g.add_edge(18, 19);
g.add_edge(19, 20);
g.add_edge(20, 21);
g.add_edge(19, 16);
g.add_edge(20, 15);
g.add_edge(16,19);
return 0;
}
Please help
Aucun commentaire:
Enregistrer un commentaire