#include <vector>
#include <list>
#include <iostream>
class DFS{
private:
struct vertex{
int data;
bool visited;
vertex(int d_=-1, bool v_=false) : data(d_), visited(v_) {}
};
std::vector<std::list<vertex>> G;
public:
DFS(int vertices);
vertex addVertex(int data);
void addEdge(int index, int data);
void dfs(int vertex);
void printGraph();
};
using namespace std;
DFS:: DFS(int vertices) : G(vertices)
{ }
DFS::vertex DFS::addVertex(int data)
{ return vertex(data, false); }
void DFS:: addEdge(int index, int data)
{
size_t gInsert = index;
if ( index >= G.size() )
{
G.push_back(std::list<vertex>());
gInsert = G.size() - 1;
}
G[gInsert].push_back(vertex(data, false));
}
void DFS::printGraph()
{
for(size_t i=0; i<G.size(); i++)
{
cout<<"Graph: "<<endl;
std::list<vertex>& ref = G[i];
if ( ref.empty())
cout << "no vertices found";
else
{
auto iter = ref.begin();
while (iter != ref.end())
{
cout << iter->data<<"->";
++iter;
}
}
cout<<endl;
}
}
void DFS:: dfs(int vertex){
}
int main(){
DFS dfs(5);
dfs.addEdge(0,1);
dfs.addEdge(0,4);
dfs.addEdge(1,2);
dfs.addEdge(1,3);
dfs.addEdge(1,4);
dfs.addEdge(2,3);
dfs.addEdge(3,4);
dfs.printGraph();
return 0;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCmNsYXNzIERGU3sKcHJpdmF0ZToKICAgIHN0cnVjdCB2ZXJ0ZXh7CiAgICAgICAgaW50IGRhdGE7CiAgICAgICAgYm9vbCB2aXNpdGVkOwogICAgICAgIHZlcnRleChpbnQgZF89LTEsIGJvb2wgdl89ZmFsc2UpIDogZGF0YShkXyksIHZpc2l0ZWQodl8pIHt9CiAgICB9OwogICAgc3RkOjp2ZWN0b3I8c3RkOjpsaXN0PHZlcnRleD4+IEc7CgpwdWJsaWM6CiAgICBERlMoaW50IHZlcnRpY2VzKTsKICAgIHZlcnRleCBhZGRWZXJ0ZXgoaW50IGRhdGEpOwogICAgdm9pZCBhZGRFZGdlKGludCBpbmRleCwgaW50IGRhdGEpOwogICAgdm9pZCBkZnMoaW50IHZlcnRleCk7CiAgICB2b2lkIHByaW50R3JhcGgoKTsKfTsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CkRGUzo6IERGUyhpbnQgdmVydGljZXMpIDogRyh2ZXJ0aWNlcykKeyB9CgpERlM6OnZlcnRleCBERlM6OmFkZFZlcnRleChpbnQgZGF0YSkKeyByZXR1cm4gdmVydGV4KGRhdGEsIGZhbHNlKTsgfQoKdm9pZCBERlM6OiBhZGRFZGdlKGludCBpbmRleCwgaW50IGRhdGEpCnsKICAgIHNpemVfdCBnSW5zZXJ0ID0gaW5kZXg7CiAgICBpZiAoIGluZGV4ID49IEcuc2l6ZSgpICkKICAgIHsKICAgICAgICBHLnB1c2hfYmFjayhzdGQ6Omxpc3Q8dmVydGV4PigpKTsKICAgICAgICBnSW5zZXJ0ID0gRy5zaXplKCkgLSAxOwogICAgfQogICAgR1tnSW5zZXJ0XS5wdXNoX2JhY2sodmVydGV4KGRhdGEsIGZhbHNlKSk7Cn0KCnZvaWQgREZTOjpwcmludEdyYXBoKCkKewoJZm9yKHNpemVfdCBpPTA7IGk8Ry5zaXplKCk7IGkrKykKCXsKCQljb3V0PDwiR3JhcGg6ICI8PGVuZGw7CgkJc3RkOjpsaXN0PHZlcnRleD4mIHJlZiA9IEdbaV07CgkJaWYgKCByZWYuZW1wdHkoKSkKCQkJY291dCA8PCAibm8gdmVydGljZXMgZm91bmQiOwoJCWVsc2UKCQl7CgkJCWF1dG8gaXRlciA9IHJlZi5iZWdpbigpOwoJCQl3aGlsZSAoaXRlciAhPSByZWYuZW5kKCkpCgkJCXsKCQkJCWNvdXQgPDwgaXRlci0+ZGF0YTw8Ii0+IjsKCQkJCSsraXRlcjsKCQkJfQoJCX0KCQljb3V0PDxlbmRsOwoJfQp9CgoKdm9pZCBERlM6OiBkZnMoaW50IHZlcnRleCl7Cgp9CgoKaW50IG1haW4oKXsKICAgIERGUyBkZnMoNSk7CiAgICBkZnMuYWRkRWRnZSgwLDEpOwogICAgZGZzLmFkZEVkZ2UoMCw0KTsKICAgIGRmcy5hZGRFZGdlKDEsMik7CiAgICBkZnMuYWRkRWRnZSgxLDMpOwogICAgZGZzLmFkZEVkZ2UoMSw0KTsKICAgIGRmcy5hZGRFZGdlKDIsMyk7CiAgICBkZnMuYWRkRWRnZSgzLDQpOwoKICAgIGRmcy5wcmludEdyYXBoKCk7CiAgICByZXR1cm4gMDsgICAKCn0K