From logic we know that p-->~p is a logical contradiction.

   We also know that ~p-->p is a logical contradiction.

   This provides us with a neat trick if we look for strongly connected
   components in the graph hint #1 leads you to build.  

   What property within a strongly connected component would be a sign 
   of a logical contradiction?