Topological sort using recursive DFS

Question

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

• Edward: Links can rot. Please include a description of the challenge here in your question.
• abhishek_naik: @Edward, the challenge description is not really needed, I think. I included it just so explain the weird format of the input.

Answer 1

First, there are some problems with your code:

1. You allocate memory for bool *visited but never free it again. Use delete[] visited when you don't need it anymore.
2. The condition in if(f<=rhs.f && f>=rhs.f) is true if and only if f == rhs.f. If that was what you wanted to check, then code it that way.
3. In line 26 you define the global variable i which is never used because it is hidden by the definition of a local i in main(), line 66.

These aside your code could be improved in the following ways:

Avoid mixing C and C++ programming styles

1. When choosing C++ and STL, go all the way. You already use std::vector for storing edges and nodes, so use one for visited. A vector does memory allocation and deallocation for you which is less error prone.

2. Use C++'s std::cout and std::cin instead of C's printf and scanf functions. See this answer for reasons why.

3. Stick to a set of rules for formatting your code. For example, you're inconsistent when it comes to spaces in variable definitions (see lines 26 and 27) and for statements (see lines 32 and 70) and when using {} brackets with single statement if and for scopes (see loops in lines 32 and 47).

4. Don't use global variables unless you have to. The definitions of node1 and node2 for example can be moved where they are needed, and myTime could be changed into a static variable of your dfsVisit function. To eleminate the other global definitions you can for example define them in main and pass them as needed by reference to dfs.

5. Move the definition of i inside the for statement where it is used. There is no need for it outside the fors scope.

6. Do bounds checking as early as possible. You know that M and N have to be between 0 and 100, so check them once you read them. Also do something when you detect an error, don't just silently ignore invalid node values.

7. Use node values starting by 1. Currently you read the value, decrease it by 1 and add 1 again to print it. Your program never relies on zero based node values.

8. Set node1.value once per rule by moving the statement one scope up because if never changes in the while loop at line 78.

9. When swapping the order of your dfsVisit and dfs functions you don't need the forward declaration of dfsVisit anymore.

10. Your nodes get copied alot. Each edge gets a copy of two nodes. You could instead use a std::map<int, node> for storing your nodes by value. An edge is then simply a pair of node values.

11. Consider an extra struct edge instead of using std::pair. Yes, it is extra code you don't necessarily need, but using edge.source and edge.target is more expressive than edge.first and edge.second which could be anything.

12. visited is a property of a node, so add bool node::visited and use this value instead of an external variable. Doesn't work unless you also implement #10, because the other edges' copies of the node don't get automagically updated when you set node.visited to true.

Consider an object oriented style instead of functional programming

If you encapsulate your algorithm in a class you can easily get rid of the global variables. Implement class methods for data input and validation and for the actual DFS. You could even split data management and DFS implementation into separate classes.