Detecting cycle in a graph

1) If the graph is undirected: Do a DFS/BFS, if you visit a previously visited node we have a cycle.

2) In a directed graph: a) Do a DFS and mark start and finish time for each node
b) Find back edges. Each back edge (u,v) has following property: start[u] <= start[v] and finish[v]<=finish[u]

c) Back edges => cycle

Important subtleties: 1) In the condition: start[u] <= start[v] and finish[v]<=finish[u], the equality corresponds to self edges, be sure to include equality if your graph can have self edges.
2) In the implementation of DFS is non-recursive, remember that a node is marked visited when it is popped from the stack and not when it is inserted in the stack.
while(stack s is not empty)
{
         u = s.pop();
         if(visited[u] ==true)
                       continue;
         visited[u] = true;
         for all nodes v adjacent to u
                      if(v is unvisited)
                              s.push(v)
}


http://www.spoj.com/problems/EPIC1304/

Precision of cout

Default precision of cout is 6. For higher precision(say 10) use cout<<std::setprecision(10)<<value;
setprecision function is in iomanip header.

However if you have something like cout<<setprecision(1)<<4.0+4.0;
You will get output as 8 and not 8.0.
To get that use std::fixed.
cout<<fixed<<setprecision(1)<<4.0+4.0; gives 8.0

Fast Expontiation iterative version

long pow(long a, long x)
{
      long res = 1;
      while(x>0){
      if(x%2!=0)
      {
            res = res* a;
       }
      x = x/2;
      a = a*a;
 }
}

How to calculate nCk%p

1) Calculating nCk: simply calculate:
numerator = n(n-1)...(n-k+1)
deno = k(k-1)...k!
ans = num/deno

But what if num and deno is high and over flow may occur, you can use
nCk = nC(k-1) (n-k+1)/k repeatedly. . Both can be calculated in O(k) steps

2) With modulo involved, suppose you are calculating modulo a big prime P. Then we know Z_p is a field and therefore multiplicative inverse exist i.e. for any number x<P, there exist x^-1 also less than P s.t. (x*x^-1)%P = 1.

So, to find nC(k-1)*(n-k+1)k^-1, we need to find k^-1. 

Before moving on let's review the fermat's little theorem, which states that for any a<p, a^(P-1) %P= 1. (The theorem is valid for a>p as well, but for our case a<p suffices). P is a  prime here. So what is k^-1%P?
k^(P-1)%P = 1 => k^-1 = k^-1k^(P-1) = k^(P-2)

Quick little fact about run time in Competitive programming

10^7 steps will take around 1 sec roughly. Though it depends on what the steps are and in codechef timelimit in the problem is for 1 test file which can contain multiple test cases.
At time of execution multiple test files may be run which is why the execution time shown may be greater than the time limit in the problem

Rounding double to integer in C++

You can use round() but that returns a floating point number which on conversion to integer may create problems for large integers (don't know why, but this has been my experience). There is an easy trick to do this, simply use:
int rounded = (int)(floating_number+0.5)

Why do competitive programmers prefer scanf() and printf() over cin and cout in C++?

AFAIK it is not a good habit to mix c and c++ codes. printf() and scanf() are C I/O functions. In C++, I should use cin and cout, yet I see many ppl using scanf() and printf() in competitive programming scenarios. The aim is to achieve improvement in time.

I feel that no problem setter should set a problem where the use of fast I/O is the critical step as that would mean inculcating bad practice. I recently came across one such problem in code chef:
http://www.codechef.com/JAN14/problems/FGFS/

Here,  using cin for input gave me a TLE (time limit exceed) error, while the answer got accepted with scanf().  May be my algorithm was not optimal, but in my knowledge my algorithm is the most used algorithm for the above problem.
May be I should post this question on Quora.(http://www.quora.com/C++-programming-language/Why-do-competitive-programmers-prefer-scanf-and-printf-over-cin-and-cout-in-C++)