# Strongly connected components in a graph: Kosaraju's algorithm

I implemented Kosaraju's algorithm on a graph with 800k vertices and 5100k edges. The time taken by various operations are: building graph took 11.84 seconds ordering took 2.54 seconds finding SCCs took 2.63 seconds My computer has an i7 with 4GB RAM. I would like to know if my code can be made more efficient. How can I improve the way I've approached the problem?

def makeGraph(txtfile):
'''Makes a graph(defaultdict) from given text file
Input: txt, each line's first element gives tail, next is head of an edge
Output: defaultdict, each vertex as a key with two values'''
Graph = defaultdict(lambda:[[],[]])
with open(txtfile) as graphRep:
for line in graphRep:
return Graph

def dfs_Order_main(G):
''' outer loop for dfs call, iterates through each vertex
calls dfs on it if has not been explored
Input: Graph(defaultdict)
Output: Order(dict)'''
Order = {} #stores time taken to explore a vertex
count =[1]
toVisit = []
visited = set()
for vert in range(1,len(G.keys())+1):
if vert not in visited:
dfs_Order(G,vert,Order,visited,count)
return Order

def dfs_Order(G,vert,Order,visited,count):
toVisit = [vert]
while len(toVisit)>0:
nextNode = toVisit[-1] #LIFO
if G[nextNode][1] == []: #no more edges to explore (terminating condition)
v = toVisit.pop()
Order[count[0]]=v #store time
count[0] +=1
else:
for i in G[nextNode][1]:
if i not in visited:
toVisit.append(i)
G[nextNode][1] = [] #after adding a vertex's edges, set it to []
return                                    #used as terminating condition

def dfs_scc_main(G,order):
''' outer loop for dfs call, iterates through each vertex
calls dfs on it if has not been explored
Input: Graph(defaultdict),order in which vertices are to be explored
Output: scc(defaultdict), strongly connected components'''
scc = defaultdict(int)
toVisit = []
visited = set()
for i in range(len(order),0,-1): #traverse in decreasing order of time
vert = order[i]                         #taken to explore a vertex
if vert not in visited:
dfs_scc(G,vert,scc,visited)
return scc

while len(toVisit)>0:
nextNode = toVisit[-1]
if G[nextNode][0] == []: