I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. Kindly review my working code below and provide me with feedback. The exact question for the below code is here.
#include<cstdio>
#include<set>
#include<list>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<functional>
struct node
{
int d, f, value;
bool operator< (const node &rhs) const
{
if(f<=rhs.f && f>=rhs.f)
return value<rhs.value;
else
return f<rhs.f;
}
};
std::vector< std::pair<node, node> > Edges;
std::set<node> s;
bool *visited;
int N, myTime=0,i=0;
node node1, node2;
void dfsVisit(node);
void dfs()
{
for(std::vector< std::pair<node, node> >::iterator it=Edges.begin(); it!=Edges.end(); it++)
if(it->first.value<N)
if(!visited[it->first.value])
dfsVisit(it->first);
}
void dfsVisit(node n)
{
myTime++; //increment myTime
n.d=myTime; //set the discovery time for node n
if(n.value<N)
if(visited[n.value])
return;
for(std::vector< std::pair<node,node> >::iterator it=Edges.begin(); it!=Edges.end(); ++it)
{
if(it->first.value==n.value && !visited[it->second.value])
{
dfsVisit(it->second);
}
}
visited[n.value]=true;
myTime++;
n.f=myTime;
//printf("The discovery and finishing times of %d are: %d, %d\n",n.value+1,n.d,n.f);
//printf("Inserting %d into the set.\n",n.value+1);
s.insert(n);
}
int main()
{
int M, firstOfRule, secondOfRule, data, i;
scanf("%d""%d",&N,&M);
visited=new bool[N];
for(i=0;i<N;i++)
visited[i]=false;
while(M--)
{
scanf("%d",&firstOfRule);
scanf("%d",&secondOfRule);
while(secondOfRule--)
{
scanf("%d",&data);
node1.value=firstOfRule-1;
node2.value=data-1;
Edges.push_back(std::make_pair(node1,node2));
printf("Connected %d and %d\n",node1.value+1,node2.value+1);
}
}
dfs();
for(std::set<node>::const_iterator it=s.begin(); it!=s.end(); it++)
printf("%d ",it->value+1);
return 0;
}
Sample input would be as follows:
5 4
3 2 1 5
2 2 5 3
4 1 3
5 1 1
And the expected output is:
1 5 3 2 4