import sys
sys.stdin = open('E:/orgraph.txt','r')
n, m = map(int, sys.stdin.readline().split())
msm = [set([]) for i in range(n+ 1 )]
for i in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    msm[v1].add(v2)
sys.stdin.close()

trail = [set() for i in range(n+ 1 )]
c = set()

def foo(a):
    global c
    c = c | a
    b = set()
    for x in a:
        for y in msm[x]:
            if y in trail[x]:
                return True
            trail[y] = trail[y] | trail[x] | set([x])
        b = b | msm[x]
    if b:
        return foo(b)
    return False
    
for z in range( 1 ,n+ 1 ):
    if not(z in c):
        res = foo(set([z]))
        if res:
            print 'Обнаружен цикл, проходящий через вершину №', z
            break
else:
    print 'Циклов нет'


------------- msm[0..N] -- это матрица смежности вида:
set([])
set([ 3 ,  4 ,  5 ])
set([ 5 ,  6 ,  7 ])
set([])
set([ 3 ])
set([])
set([ 1 ])
set([])
set([ 2 ,  7 ])
set([ 1 ,  11 ])
set([ 9 ])
set([ 10 ])

------------- в файле:
 11   14  ------- <-- число вершин и ребер (нумерую с единицы)
 1   5 
 4   3 
 8   2 
 2   7 
 2   5 
 2   6 
 6   1 
 1   4 
 1   3 
 8   7 
 9   1 
 9   11 
 11   10 
 10   9 

 95   3715 
-- 76 18 -- добавки
-- 18 95 --
-- 95 33 --
-- 33 50 --
-- 50 76 --
 1   3 
 1   5 
 1   6 
 1   8 
 1   10 
 1   11 
 1   12 
 1   14 
 1   16 
 1   17 
.. ..
.. ..
 89   94 
 90   91 
 90   92 
 90   93 
 90   94 
 91   92 
 91   93 
 91   94 
 92   93 
 92   94 
 93   94 

 11  --->-- 10
 \        /
  \_    |/_
  |\    /
    \  /
      9 
     |
     |
    \|/
     |
     |

import sys

#sys.stdin = open('E:/orgraph.txt','r')
sys.stdin = open('E:/p95v3710e.txt','r')
n, m = map(int, sys.stdin.readline().split())
msm = [set() for i in range(n+ 1 )]
for i in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    msm[v1].add(v2)
sys.stdin.close()


trail = [set() for i in range(n+ 1 )]
c = set()

def foo(a):
    global c
    global trail
    c = c | a
    b = set()
    for x in a:
        for y in msm[x]:
            if y in trail[x]:
                return y
            trail[y] = trail[y] | trail[x] | set([x])
        b = b | msm[x]
    if b:
        return foo(b)
    return  0 


from time import time
t = time()

for z in range( 1 , n+ 1 ):
    if not(z in c):
        res = foo(set([z]))
        if res:
            print 'Обнаружен цикл, проходящий через вершину №', res
            break
        for j in range( 1 , n+ 1 ):
            if j in c:
                msm[j] = set()
            else:
                msm[j] = msm[j] - c
else:
    print 'Циклов нет'

print time() - t

/*
For this program you will implement a graph cycle detector. The program
will
input a directed graph and output all simple cycles (see p88), if any,
that
exist in the graph. Specifically,

1.   Your program may use no global variables.

2.   Implement a graph data structure (either adjacency matrix or
adjacency
     list) to hold the directed graph. The graph must be allocated and
     deallocated at runtime. Implement procedures for graph allocation,
    graph deallocation, edge addition and edge lookup.

3.   Implement procedures for detecting (and outputting) cycles in a
given
     graph. A cycle should be output as a directed path starting from
the
     smallest vertex number, e.g., '1 -> 2 -> 3 -> 5 -> 1'. Cycles
should be
     output in non-decreasing order by their starting vertex, where
cycles
     beginning with the same vertex can be output in any order. If the
graph
     contains no cycles, then simply output 'No cycles'.

4.   The main part of your program will read in data from a file whose
name
     is given as the first argument to your executable. The first line
of
     the file contains the number of vertices (1-100) and edges (1-1000)
in
     the graph. The remaining lines define the edges in the graph in the
    form 'e 5 3', which means there is a directed edge in the graph from
    vertex 5 to vertex 3. Your main program should read in the graph and
    then call your procedure to output any cycles. 

*/

/* Anan Tongprasith */
/* Compile: cc graph.c */
/**********************/
#include<stdio.h>
#include<stdlib.h>

/* This program use adjacency matrix */

/************* list of all functions **************/

/* insert a new row in the middle of array ba */
int arrayshift(int ba[ 100 ][ 20 ],int i,int nodenum);

/* detect a cycle */
int cycledetec(int **A,int startp,int nodenum);

/* add an edge, m=start vertice, n=end vertice */
void graphadd(int **A,int m,int n);

/* allocate memory for the matrix */
int **graphalloc(int nodenum);

/* free memory */
void graphfree(int **A,int nodenum);

/**************************************************/

int main(int argc,char *argv[])
{ FILE *fp;char newline[ 10 ],*tempch=" ";
  int nodenum,edgenum,i,j,**A,mybegin,myend;

/* open the input file */
	fp=fopen(argv[ 1 ],"r");
	fgets(newline, 10 ,fp);

/* reading # of node */
	sscanf(newline,"%i %i",&nodenum,&edgenum);

/* allocating the adjacency matrix */
	A=graphalloc(nodenum);

/* reading the input file and adding to the matrix*/
	while(fgets(newline, 10 ,fp) != NULL)
	{ 
	   sscanf(newline,"%s %i %i",tempch,&mybegin,&myend);
	   graphadd(A,mybegin- 1 ,myend- 1 );
	}
	fclose(fp);
	j= 0 ;

/* detecting cycle from starting point i (1,2,3,4,5) */
	for(i= 0 ;i<nodenum;i++)
		if(cycledetec(A,i,nodenum)== 1 ) j+= 1 ;
	if(j== 0 )
		printf("No cycle\n");
	/*for(i=0;i<nodenum;i++)
	{
	  for(j=0;j<nodenum;j++)
	  	printf("%i ",A[i][j]);
	  printf("\n");
	}*/

/* freeing the matrix */
	graphfree(A,nodenum);
}

/* detect cycle beginning from startp */
/* how? brute force */
/* 1. find all existing paths with distance = mydist*/
/*    those paths must have really existing subpaths */
/* 2. put all those paths into "bigarray" */
/* 3. checking if those paths have redundant node? if so, throw away */
/* 4. checking if there is a path from the last node to the first node*/
/* 5. increase mydist and go back to 1. */
/****************************************/

int cycledetec(int **A,int startp,int nodenum)
{ int maxdist=nodenum-startp,cycle= 0 ,mydist,i,subdist,bigarray[ 100 ][ 20 ];
  int index,j,k,l;

/* checking for distance = 1, for examples, 4 -> 4, 3 -> 3 */ 
	if(A[startp][startp]== 1 )		/* mydist=0 */
	{  printf("%i -> %i\n",startp+ 1 ,startp+ 1 );
	   cycle= 1 ;
	}

/* checking for distance > 1 */
/****** outer loop check from distance = 2 to maximum distance
	(when startp=1) ********/

	for(mydist= 1 ;mydist<maxdist;mydist++) 
	{	
		for(i= 0 ;i< 100 ;i++)	/* assume possible route < 100 */
		{  for(index= 0 ;index<nodenum;index++)
		   bigarray[i][index]=- 1 ;
	   	   bigarray[i][ 0 ]=startp;
		}		/* this loop initialize the bigarray */
		index= 0 ;
/******* now start to fill in the bigarray **********/
/******* each row in the big array is an existing route *********/
/******* each possible route is already checked for existance of*****/
/******* subpath before being put in the bigarray ******/
/******* the bigarray are cleared when start looking the next distance */

	/* this subloop keep checking until reaching the wanted distance */	
	for(subdist= 1 ;subdist<=mydist;subdist++)  
		{
		   index= 0 ;

	/* node in the middle should be numbered less than starter */
		   for(i=startp+ 1 ;i<nodenum;i++)
		   {
			if(bigarray[index][subdist- 1 ]>= 0 &&A[bigarray[index][subdist- 1 ]][i]!= 0 ) /****** checking path from last point to current point *****/
			{	bigarray[index][subdist]=i;
				arrayshift(bigarray,index,nodenum);
				index+= 1 ;
				bigarray[index][subdist- 1 ]=bigarray[index- 1 ][subdist- 1 ];
			}
		   }
		}	
	/* After reaching the wanted distance, checking path from the
last nodes in all existing path back to the starting point */

		for(i= 0 ;i<index;i++)
		{	l= 0 ;

			/* this loop check for repeated node */
			/* ex. 1->3->3->4 , throw it away*/
			for(j= 0 ;j<=mydist;j++)
			{   for(k= 0 ;k<=mydist;k++)
			    {	if(j!=k && bigarray[i][j]==bigarray[i][k])
					l+= 1 ;
			    }
			}

			/* no repeated node? check for path from */
			/* the last node to startp */

			if(l== 0 &&A[bigarray[i][mydist]][startp]== 1 )
			{  for(j= 0 ;j<=mydist;j++)
			   	printf("%i -> ",bigarray[i][j]+ 1 );
			   printf("%i\n",startp+ 1 );
			   cycle= 1 ;	/* found a cycle */
			}
		}
	} 
	return cycle;
}
/* making rooms */
int arrayshift(int ba[ 100 ][ 20 ],int index,int nodenum)
{ int i,j;
	for(i= 98 ;i>index;i--)
	{  for(j= 0 ;j<nodenum;j++)
		ba[i+ 1 ][j]=ba[i][j];
	}
}
void graphadd(int **A,int m,int n)
{	A[m][n]= 1 ;
}
int **graphalloc(int nodenum)
{ int **A,i,j;
	A=malloc(nodenum* 8 );
	for(i= 0 ;i<nodenum;i++)
	{ A[i]=malloc(nodenum* 4 );
	  for(j= 0 ;j<nodenum;j++)
		A[i][j]= 0 ;
	}
	return A;
}
void graphfree(int **A,int nodenum)
{ int i;
	for(i= 0 ;i<nodenum;i++)
	{ free(A[i]);
	}
	free(A);
}

procedure foo(r: longint);
var i: longint;
begin
inc(sch); h[sch]:=r; a[r, 0 ]:=- 1 ;
for i:= 1  to n do if a[i,r]= 1  then
begin dec(a[i, 0 ]); if a[i, 0 ]= 0  then foo(i); end;
end;

import networkx as nx

g = nx.DiGraph()

import sys
sys.stdin = open('E:/p95.txt', 'r')
sys.stdin.readline()
for i in range( 3710 ):
    e = map(int, sys.stdin.readline().split())
    g.add_edge(e)
sys.stdin.close()


from time import time
t = time()

print nx.is_directed_acyclic_graph(g)

print time() - t




>>> 
True
 0 . 0150001049042 

import networkx

def is_directed_acyclic_graph(G):
    """Return True if the graph G is a directed acyclic graph (DAG).

    Otherwise return False.
    
    """
    if topological_sort(G) is None:
        return False
    else:
        return True

def topological_sort(G):
    """
    Return a list of nodes of the digraph G in topological sort order.

    A topological sort is a nonunique permutation of the nodes
    such that an edge from u to v implies that u appears before v in the
    topological sort order.

    If G is not a directed acyclic graph no topological sort exists
    and the Python keyword None is returned.

    This algorithm is based on a description and proof at
    http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm

    See also is_directed_acyclic_graph()
    
    """
    # nonrecursive version

    seen={}
    order_explored=[] # provide order and 
    explored={}       # fast search without more general priorityDictionary
                     
    if not G.is_directed():  G.successors_iter=G.neighbors_iter

    for v in G.nodes_iter():     # process all vertices in G
        if v in explored: continue

        fringe=[v]   # nodes yet to look at
        while fringe:
            w=fringe[- 1 ]  # depth first search
            if w in explored: # already looked down this branch
                fringe.pop()
                continue
            seen[w]= 1      # mark as seen
            # Check successors for cycles and for new nodes
            new_nodes=[]
            for n in G.successors_iter(w):  
                if n not in explored:
                    if n in seen: return #CYCLE !!
                    new_nodes.append(n)
            if new_nodes:   # Add new_nodes to fringe
                fringe.extend(new_nodes)
            else:           # No new nodes so w is fully explored
                explored[w]= 1 
                order_explored.insert( 0 ,w) # reverse order explored
                fringe.pop()    # done considering this node
    return order_explored

def topological_sort_recursive(G):
    """
    Return a list of nodes of the digraph G in topological sort order.

    This is a recursive version of topological sort.
    
    """
    # function for recursive dfs
    def _dfs(G,seen,explored,v):
        seen[v]= 1 
        for w in G.successors(v):
            if w not in seen: 
                if not _dfs(G,seen,explored,w):
                    return
            elif w in seen and w not in explored:
                # cycle Found--- no topological sort
                return False
        explored.insert( 0 ,v) # inverse order of when explored 
        return v

    seen={}
    explored=[]

    if not G.is_directed():  G.successors=G.neighbors
    
    for v in G.nodes_iter():  # process all nodes
        if v not in explored:
            if not _dfs(G,seen,explored,v): 
                return 
    return explored

Level      Node
----------------
 1000         A 
 2000         B

          A--> B <---D
                \
                 \
                  _/
                   C

Level      Node
----------------
 1000         A 
 1000         D
 2000         B
 3000         C

#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

const int n= 1000 ;     //--ожидаемое число вершин; нумеруем с 1

bitset<n+ 1 > np;     //--битсет для обновления списков предков части вершин
bitset<n+ 1 > pr[n+ 1 ];  //--в этих битсетах храним списки предков всех вершин
vector<int> msm[n+ 1 ];   //--матрица смежности
vector<int> v( 1 );
int v1,v2;
int res;


int foo(vector<int> &v) {
    vector<int> w;
    for (int i= 0 ; i<v.size(); ++i) {
        if (np.test(v[i])) return v[i]; //-- в добавочном списке предков
                           //-- обнаружена сама вершина v[i]! -- Цикл!
        pr[v[i]]=pr[v[i]] | np; //-- обновляем список предков вершины v[i]
        w.insert(w.end(),msm[v[i]].begin(),msm[v[i]].end()); //-- формируем
                                                             //-- новую волну
    }
    if (w.empty()) return  0 ;
    else return foo(w); //-- гоним очередной гребень, если есть что гнать
}


FILE *fp=fopen("E:\\p95.txt","r");

int main() {
    for (int j= 0 ; j< 3710 ; ++j) {
        fscanf(fp,"%d%d",&v1,&v2);   //-- читаем очередное ребро (v1 -> v2)
        msm[v1].push_back(v2);     //-- добавляем в матрицу смежности
        np=pr[v1];               //-- это битсет для обновления списков предков
        np.set(v1);               //-- ставим бит и для v1
        v[ 0 ]=v2;                   //-- начинаем обновление с вершины v2
        res=foo(v);                 //-- гоним волну от вершины v2
        if (res!= 0 ) {
            cout << "Cycle at vertex #" << res << "\n";
            break;
        }
    }

    fclose(fp);
    if (res== 0 ) cout << "No cycles!\n";

cin >> res;
return  0 ;
}