Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Depth First Search

  Depth-first search (DFS) follows the strategy to search ”deeper” in the graph whenever possible. In DFS, edges are recursively explored out of the most recently discovered vertex $v$ that still has unexplored edges leaving it. When all of $v$'s edges have been explored, the search ”backtracks” to explore edges leaving the vertex from which $v$ was discovered.

  This process continues until all the vertices that are reachable from the original source vertex have been discovered. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source.

  DFS timestamps each vertex as follows:

$d[v]$ records when $v$ is first discovered.

$f[v]$ records when the search finishes examining $v$’s adjacency list.

  Write a program which reads a directed graph $G = (V, E)$ and demonstrates DFS on the graph based on the following rules:

$G$ is given in an adjacency-list. Vertices are identified by IDs $1, 2,... n$ respectively.

IDs in the adjacency list are arranged in ascending order.

The program should report the discover time and the finish time for each vertex.

When there are several candidates to visit during DFS, the algorithm should select the vertex with the smallest ID.

The timestamp starts with 1.

Input

  In the first line, an integer $n$ denoting the number of vertices of $G$ is given. In the next $n$ lines, adjacency lists of $u$ are given in the following format:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ is ID of the vertex and $k$ denotes its degree. $v_i$ are IDs of vertices adjacent to $u$.

Output

  For each vertex, print $id$, $d$ and $f$ separated by a space character in a line. $id$ is ID of the vertex, $d$ and $f$ is the discover time and the finish time respectively. Print in order of vertex IDs.

Constraints

$1 \leq n \leq 100$

Sample Input 1

4
1 1 2
2 1 4
3 0
4 1 3

Sample Output 1

1 1 8
2 2 7
3 4 5
4 3 6

Sample Input 2

6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

Sample Output 2

1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6

  This is example for Sample Input 2 (discover/finish)

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
4
1 1 2
2 1 4
3 0
4 1 3


Sample output:
1 1 8
2 2 7
3 4 5
4 3 6

Submission status: Accepted

Solution code:
n=0
m=input()
c=[0 for i in xrange(m)]
ts=[0 for i in xrange(m)]


def dfs_visit(u):
    global n
    if ts[u]:return
    n = n + 1
    ts[u]=[u+1,n]
    for i in c[u]:dfs_visit(i-1)
    n = n + 1
    ts[u][2:]=[n]

def dfs():
    for i in range(m):
     l=map(int,raw_input().split())
     c[l[0]-1]=l[2:]
    for i in range(m):
     dfs_visit(i)
     print " ".join(map(str,ts[i]))

dfs()

Submission status: Accepted

Solution code:
n = int( raw_input() )
   
d = [ 0 for i in range(n) ]
f = [ 0 for i in range(n) ]
G = [ 0 for i in range(n) ]
v = [ [0 for i in range(n) ] for j in range(n) ]
st = [ 0 for i in range(n) ]
tm = [ 0 ]
   
def DFS_visit(s):
  st[ s ] = 1
  tm[ 0 ] += 1
  d[ s ] = tm[ 0 ]
  for e in range(n):
    if v[ s ][ e ] == 1 and st[ e ] == 0:
      DFS_visit(e)
  st[ s ] == 2
  tm[ 0 ] += 1
  f[ s ] = tm[ 0 ]
   
def DFS():
  for s in range(n):
    if st[ s ] == 0:
      DFS_visit(s)
  for s in range(n):
     print'{0} {1} {2}'.format( s+1 , d[ s ] , f[ s ] )
       
for i in range(n):
  G = map( int , raw_input().split() )
  for j in range( G[1] ):
    v[ G[0] -1 ][ G[ 2+j ] -1 ] = 1
   
DFS()

Submission status: Accepted

Solution code:
n = int(raw_input())
 
def dfs(u,t):
    global graph
    global found
    global timestamp
 
    if u in found: return t
    found.add(u)
    timestamp[u] = [-1,-1]
    timestamp[u][0] = t
    t += 1
    for v in graph[u]:
        t = dfs(v,t)
    timestamp[u][1] = t
    t += 1
    return t
 
graph = [[] for i in range(n)]
found = set()
timestamp = {}
 
for i in range(n):
    entry = map(int,raw_input().strip().split(' '))
    u = entry[0]
    u -= 1
    for v in entry[2:]:
        v -= 1
        graph[u].append(v)
 
 
t = 1
for i in range(n):
    t = dfs(i,t)
 
for i in timestamp:
    print i+1,timestamp[i][0],timestamp[i][1]

Submission status: Accepted

Solution code:
n = input()

d     = [0 for i in range(n)]
f     = [0 for i in range(n)]
G     = [0 for i in range(n)]
M     = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
tt    = [0]
WHITE = 0
GRAY  = 1
BLACK = 2

def dfs_visit(u):
    color[u] = GRAY
    tt[0] = tt[0] + 1
    d[u] = tt[0]
    for v in range(n):
        if M[u][v] == 0:
            continue
        if color[v] == WHITE:
            dfs_visit(v)
    color[u] == BLACK
    tt[0] = tt[0] + 1
    f[u] = tt[0]

def dfs():
    for u in range(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in range(n):
        print "%d %d %d" %(u + 1, d[u], f[u])

### MAIN
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1

dfs()

Submission status: Accepted

Solution code:
n = int(raw_input())
N = 100
WHITE = 0
GRAY = 1
BLACK = 2
Color = [WHITE for i in range(n)]
#M = [[0 for i in range(N)] for j in range(N)]
tt = 0
d = [0 for i in range(n)]
f = [0 for i in range(n)]
def dfs_visit(u):
    Color[u] = GRAY
    global tt
    tt += 1
    d[u] = tt
    for v in range(n):
        if M[u][v] == 0:
            continue
        if Color[v] == WHITE:
            dfs_visit(v)
    Color[u] = BLACK 
    tt += 1
    f[u] = tt
 
def dfs():
    #Color = [WHITE for i in range(n)]
    tt = 0
     
    for u in range(n):
        if Color[u] == WHITE:
            dfs_visit(u)
    for u in range(n):
        print "%d %d %d" %(u + 1, d[u], f[u])
 
M = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    u = tmp[0]
    k = tmp[1]
    u -= 1
    for j in range(k):
        v = tmp[j + 2]
        v -= 1
        M[u][v] = 1
dfs()

Submission status: Accepted

Solution code:
n = int(raw_input())
  
d = [0 for i in range(n)]
f = [0 for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
time = [0]
g = [0 for i in range(n)]
  
  
def dfs_visit(s):
    st[s] = 1
    time[0] += 1
    d[s] = time[0]
      
    for k in range(n):  
      if a[s][k] == 1 and st[k] == 0:
          dfs_visit(k)
    st[s] ==2
    time[0] += 1
    f[s] = time[0]
  
def main():
    for s in range(n):
        if st[s] == 0:
            dfs_visit(s)
    for s in range(n):
        print '%d %d %d' %(s+1, d[s], f[s])
  
for i in range(n):
    g = map(int, raw_input().split())
    for j in range(g[1]):
        a[g[0]-1][g[2+j]-1] = 1
  
main()

Submission status: Accepted

Solution code:
def visit(u):
  global t
  flag[u] = 1
  t += 1
  s[u] = t
  for v in range(n):
    if M[u][v]==0:
      continue
    if flag[v]==0:
      visit(v)
  flag[u] = 2
  t += 1
  e[u] = t


def dfs():
  for u in range(n):
    if flag[u]==0:
      visit(u)
  for u in range(n):
    print '%d %d %d' % (u+1, s[u], e[u])


n = input()
t = 0
flag = [0 for row in range(n)]
s = [0 for row in range(n)]
e = [0 for row in range(n)]
M = [[0 for col in range(n)] for row in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  a = str[2:]
  u -= 1
  for v in a:
    M[u][v-1] = 1

dfs()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import division,print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def walk(index,tm,L,d,f):
    tm+=1
    d[index]=tm
    for i in L[index]:
        if not d[i-1]:
            tm=walk(i-1,tm,L,d,f)
    tm+=1
    f[index]=tm
    return tm
 
def main():
    num=int(sys.stdin.readline())
    L=[]
    for _ in range(num):
        L.append([int(s) for s in sys.stdin.readline().split()[2:]])
    d=[0]*num
    f=[0]*num
    tm=0
    for i in range(num):
        if not d[i]:
            tm=walk(i,tm,L,d,f)
    for i in range(num):
        print(i+1,d[i],f[i])
 
main()

Submission status: Accepted

Solution code:
T = [0]

def curserch(N,k,T,P,n):
    T[0] = T[0]+1
    P[k]["d"] = T[0]
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            curserch(N,i,T,P,n)
            T[0] = T[0]+1
            P[i]["f"]=T[0]


n = int(input())
A = [[0 for j in range(n+1)] for i in range(n+1)]


for i in range(n):
    vec = input().split()
    u = int(vec[0])
    k = int(vec[1])
    nodes = vec[2:]
    for i in range(int(k)):
        v = int(nodes[i])
        A[u][v] = 1

P=[{"d":0} for i in range(n+1)]
for i in range(1,n+1):
    if P[i]["d"]==0:
        curserch(A,i,T,P,n)
        T[0] = T[0]+1
        P[i]["f"]=T[0]
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"])

Submission status: Accepted

Solution code:
n = int(raw_input())

d = [0] * n
f = [0] * n
M = [[0]*n for _ in xrange(n)]
color = [0] * n
tt = 0
WHITE = 0
GRAY = 1
BLACK = 2

def dfs_visit(u):
    global tt
    color[u] = GRAY
    tt += 1
    d[u] = tt
    for v in xrange(n):
        if M[u][v] == 0:
            continue
        if color[v] == WHITE:
            dfs_visit(v)
    color[u] = BLACK
    tt += 1
    f[u] = tt
    return 0

def dfs():
    for u in xrange(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in xrange(n):
        print "{} {} {}".format(u+1, d[u], f[u])
    return 0

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        u = a[0]-1
        k = a[1]
        for j in xrange(k):
            v = a[j+2] -  1
            M[u][v] = 1
    
    dfs()
    return 0

main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(raw_input())

d = [0] * n
f = [0] * n
M = [[0]*n for _ in xrange(n)]
color = [0] * n
tt = 0
WHITE = 0
GRAY = 1
BLACK = 2
nt = [0] * n

def next(u):
    for v in xrange(nt[u],n):
        nt[u] = v + 1
        if M[u][v] == 1:
            return v
    return -1

def dfs_visit(r):
    global tt
    S = deque([])
    S.append(r)
    color[r] = GRAY
    tt += 1
    d[r] = tt

    while len(S) > 0:
        u = S[len(S)-1]
        v = next(u)
        if v != -1:
            if color[v] == WHITE:
                color[v] = GRAY
                tt += 1
                d[v] = tt
                S.append(v)
        else:
            S.pop()
            color[u] = BLACK
            tt += 1
            f[u] = tt

    return 0

def dfs():
    for u in xrange(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in xrange(n):
        print "{} {} {}".format(u+1, d[u], f[u])
    
    return 0

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        u = a[0]-1
        k = a[1]
        for j in xrange(k):
            v = a[j+2] -  1
            M[u][v] = 1
    
    dfs()
    return 0

main()

Submission status: Accepted

Solution code:
def dfs(v, cnt):
    D[v] = cnt
    cnt += 1
    for c in edge[v]:
        if D[c] == -1:
            cnt = dfs(c, cnt)
    F[v] = cnt
    cnt += 1
    return cnt


V = int(input())
edge = [[] for _ in range(V)]
for _ in range(V):
    u, _, *v = map(lambda x: int(x)-1, input().split())
    edge[u] = sorted(v)
D, F = [-1] * V, [-1] * V
c = 1
for i in range(V):
    if D[i] == -1:
        c = dfs(i, c)
for i, (d, f) in enumerate(zip(D, F)):
    print(i+1, d, f)

Submission status: Accepted

Solution code:
n = int(input())
mat = [[0] * n for _ in range(n)]
d, f = [0] * n, [0] * n
for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        mat[i - 1][j - 1] = 1

time, current = 0, 0
stack = []
while 0 in f:
    if not stack:
        for i, v in enumerate(f):
            if v == 0:
                stack.append(i)
                time += 1
                d[i] = time
                break
    time += 1
    current = stack[-1]
    for i in range(len(mat[current])):
        if mat[current][i] and not d[i]:
            current = i
            d[i] = time
            stack.append(i)
            break
    else:
        f[current] = time
        current = stack.pop()

for l in zip(range(1, n + 1), d, f):
    print(*l)

Submission status: Accepted

Solution code:
def dfs(u):
    global time
    time+=1
    color[u]='gray'
    d[u]+=time
    for v in xrange(n):
        if m[u][v]!=0 and color[v]=="white":
            dfs(v)
    time+=1
    color[u]="black"
    f[u]+=time
    

n=input()
info=[0]*n
color=["white"]*n
m=[[0]*n for _ in xrange(n)]
d=[0]*n
f=[0]*n
for i in xrange(n):
    info[i]=map(int,raw_input().split())
    if info[i][1]==0:
        pass
    else:
        for j in info[i][2:]:
            m[i][j-1]=j
time=0
for i in xrange(n):
    if color[i]=="white":
        dfs(i)
for i in xrange(n):
    print i+1,d[i],f[i]

Submission status: Accepted

Solution code:
import sys

def dfs(i):
    global V, t, d, f

    if d[i] != 0:
        return

    d[i] = t
    t += 1
    for v in V[i]:
        dfs(v)

    f[i] = t
    t += 1

    return

lines = sys.stdin.readlines()
n = int(lines[0])
V = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    v = map(int, lines[i].split())
    V[v[0]] = v[2:]
d = [0] * (n + 1)
f = [0] * (n + 1)
t = 1

flag = True
while flag:
    flag = False
    for i in range(1, n + 1):
        if d[i] == 0:
            dfs(i)
            flag = True
            break

for i in range(1, n + 1):
    print i, d[i], f[i]

Submission status: Accepted

Solution code:
"""Depth First Search."""

n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

# searched or not, number of vertex, discovery time and finishing time.
sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    path.append(u)
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not sndf[v][0]:
                sndf[v][0] = True
                time += 1
                sndf[v].append(time)
                path.append(v)
        else:
            path.pop()
            sndf[u][0] = True
            time += 1
            sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

Submission status: Accepted

Solution code:
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

# searched or not, number of vertex, discovery time and finishing time.
sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    for v in adj[u]:
        if not sndf[v][0]:
            dfs(v)
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

Submission status: Accepted

Solution code:
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

# searched or not, number of vertex, discovery time and finishing time.
sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    for v in adj[u]:
        if not sndf[v][0]:
            dfs(v)
    time += 1
    sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

Submission status: Accepted

Solution code:
def DFS(G):
    ans = [0] + [[0,0,0] for _ in range(len(G))]
    def main(G,i):
        ans[0] += 1
        ans[i] = [i, ans[0], ans[0]]
        for j in sorted(G[i-1][2:]):
            if ans[j][0] == 0: main(G,j)
        ans[0] += 1
        ans[i][2] = ans[0]
    for u in G:
        if ans[u[0]][0] == 0: main(G,u[0])
    return ans[1:]


if __name__=='__main__':
    n = int(input())
    G = [list(map(int,input().split())) for _ in range(n)]
    for out in DFS(G): print(*out)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,v):
        self.v = v
        self.c = []

def dfs(n,f,d,t,visited):
    visited.add(n.v)
    f[n.v] = t
    t2 = t
    for c in sorted(n.c,key=lambda x:x.v):
        if not c.v in visited:
            t2 = dfs(c,f,d,t2+1,visited)
    d[n.v] = t2+1
    return t2+1

n = int(raw_input())
nodes = {}
for _ in range(n):
    entry = map(int,raw_input().split(' '))
    nid = entry[0]
    if not nid in nodes: nodes[nid] = Node(nid)
    k = entry[1]
    if k > 0:
        children = entry[2:]
        for c in children:
            if not c in nodes: nodes[c] = Node(c)
            nodes[nid].c.append(nodes[c])

f = {}
d = {}
visited = set()
t = dfs(nodes[1],f,d,1,visited)
while len(visited) < len(nodes):
    for nid in nodes:
        if not nid in visited:
            t = dfs(nodes[nid],f,d,t+1,visited)

for k in f:
    print k,f[k],d[k]

Submission status: Accepted

Solution code:
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

n = int(input())
a = [0]

for i in range(n):
    v = input().split()
    v.pop(0)
    v.pop(0)
    a.append([int(x) for x in v])

debug(a)
stack = [1]
results = [[0 for i in range(2)] for j in range(n + 1)]
results[0][0] = 0
time = 0

def depth_first_search(a, stack):
    debug(a)
    debug(results)
    debug(stack)
    global time
    if len(stack) == 0:
        return

    v = stack.pop()
    if results[v][0] == 0:
        time += 1
        results[v][0] = time

    es = a[v]
    if len(es) == 0 and results[v][1] == 0:
        time += 1
        results[v][1] = time

    if len(es) != 0:
        stack.append(v)
        next_vert = es.pop(0)
        if results[next_vert][0] == 0:
            stack.append(next_vert)

    depth_first_search(a, stack)

for i in range(n):
    stack = [i + 1]
    depth_first_search(a, stack)

debug(results)

results.pop(0)

i = 1
for row in results:
    print(str(i) + " " + str(row[0]) + " " + str(row[1]))
    i += 1

Submission status: Accepted

Solution code:
time = 0

def dfs_visit(g, u):
    global time
    time += 1
    u[2] = time
    u[1] = 'g'

    for v in u[0]:
        ch = g[v]
        if ch[1] == 'w':
            ch[4] = u[5]
            dfs_visit(g, ch)
    u[1] = 'b'
    time += 1
    u[3] = time

n = int(input())

g = {}
s = 0
stack = []
for i in range(n):
    x = list(map(int, input().split()))
    g[x[0]] = [x[2:], 'w', 0, 0, None, x[0]]
    if i == 0:
        s = x[0]

for k, v in g.items():
    if v[1] == 'w':
        dfs_visit(g, v)


for i in range(n):
    node = g[i+1]
    print("{} {} {}".format(i+1, node[2], node[3]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time
    # init the first node of overall graph iterations(times >= 1)
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    # init end
    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_adj_vertices(_vertex=current_vertex)
        # print('start', current_vertex, next_vertex, vertex_status_list, vertex_visit_stack)

        if next_vertex:
            if vertex_status_list[next_vertex] is UNVISITED:
                vertex_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertex_d_time[next_vertex] += time
                vertex_visit_stack.append(next_vertex)
                # print('on', current_vertex, next_vertex, vertex_status_list, vertex_visit_stack)
        else:
            # print('no out degree', current_vertex)
            vertex_visit_stack.pop()
            vertex_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertex_f_time[current_vertex] += time
        # print('end', current_vertex, vertex_status_list, vertex_visit_stack)

    return None


def get_adj_vertices(_vertex):
    for j in range(vertex_num):
        if adj_matrix[int(_vertex) - 1][j]:
            adj_matrix[int(_vertex) - 1][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            # print('round', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num
    # config length -> (vertex_num + 1)
    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, -1)
    vertex_d_time, vertex_f_time = ([0] * (vertex_num + 1) for _ in range(2))

    adj_matrix = generate_adj(vertex_info)

    time = 1
    dfs_start()

    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time

    # init the first node of overall graph iterations(times >= 1)
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    # init end

    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_adj_vertices(_vertex=current_vertex)

        if next_vertex:
            if vertex_status_list[next_vertex] is UNVISITED:
                vertex_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertex_d_time[next_vertex] += time
                vertex_visit_stack.append(next_vertex)
        else:
            vertex_visit_stack.pop()
            vertex_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertex_f_time[current_vertex] += time

    return None


def get_adj_vertices(_vertex):
    for j in range(vertex_num):
        if adj_matrix[int(_vertex) - 1][j]:
            adj_matrix[int(_vertex) - 1][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            # print('round', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, -1)
    vertex_d_time, vertex_f_time = ([0] * (vertex_num + 1) for _ in range(2))

    adj_matrix = generate_adj_matrix(vertex_info)
    time = 1
    dfs_start()
    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time

    # init the first node of overall graph iterations(times >= 1)
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    # init end

    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_adj_vertices(vertex=current_vertex)

        if next_vertex:
            if vertex_status_list[next_vertex] is UNVISITED:
                vertex_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertex_d_time[next_vertex] += time
                vertex_visit_stack.append(next_vertex)
        else:
            vertex_visit_stack.pop()
            vertex_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertex_f_time[current_vertex] += time

    return None


def get_adj_vertices(vertex):
    index = int(vertex) - 1
    for j in range(vertex_num):
        if adj_matrix[index][j]:
            adj_matrix[index][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            # print('round', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, -1)
    vertex_d_time, vertex_f_time = ([0] * (vertex_num + 1) for _ in range(2))

    adj_matrix = generate_adj_matrix(vertex_info)
    # timing start from 1
    time = 1
    dfs_start()
    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time

    # init the first node of overall graph iterations(times >= 1)
    vertices_visit_stack.append(v_init)
    vertices_status_list[v_init] = VISITED_IN_STACK
    vertices_d_time[v_init] += time
    # init end

    while len(vertices_visit_stack) > 1:
        current_vertex = vertices_visit_stack[-1]
        next_vertex = get_adj_vertices(vertex=current_vertex)

        if next_vertex:
            if vertices_status_list[next_vertex] is UNVISITED:
                vertices_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertices_d_time[next_vertex] += time
                vertices_visit_stack.append(next_vertex)
        else:
            vertices_visit_stack.pop()
            vertices_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertices_f_time[current_vertex] += time

    return None


def get_adj_vertices(vertex):
    index = int(vertex) - 1
    for j in range(vertices_num):
        if adj_matrix[index][j]:
            adj_matrix[index][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertices_num):
        if vertices_status_list[i + 1] == UNVISITED:
            # print('round: ', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    vertices_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertices_num for _ in range(vertices_num)]
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    vertices_visit_stack = [-1]
    vertices_status_list = [UNVISITED] * vertices_num
    vertices_status_list.insert(0, -1)
    vertices_d_time, vertices_f_time = ([0] * (vertices_num + 1) for _ in range(2))

    adj_matrix = generate_adj_matrix(vertices_info)
    # timing start from 1
    time = 1
    dfs_start()
    for k in range(vertices_num):
        print(k + 1, vertices_d_time[k + 1], vertices_f_time[k + 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time

    # init the first node of overall graph iterations(times >= 1)
    vertices_visit_stack.append(v_init)
    vertices_status_list[v_init] = VISITED_IN_STACK
    vertices_d_time[v_init] += time
    # init end

    while len(vertices_visit_stack) > 1:
        current_vertex = vertices_visit_stack[-1]
        next_vertex = get_adj_vertices(vertex=current_vertex)

        if next_vertex:
            if vertices_status_list[next_vertex] is UNVISITED:
                vertices_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertices_d_time[next_vertex] += time
                vertices_visit_stack.append(next_vertex)
        else:
            vertices_visit_stack.pop()
            vertices_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertices_f_time[current_vertex] += time

    return None


def get_adj_vertices(vertex):
    index = int(vertex) - 1
    for j in range(vertices_num):
        if adj_matrix[index][j]:
            adj_matrix[index][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertices_num):
        if vertices_status_list[i + 1] == UNVISITED:
            # print('round: ', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    vertices_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = tuple([[0] * vertices_num for _ in range(vertices_num)])
    # assert len(vertex_info) == vertex_num

    # config length = (vertex_num + 1)
    vertices_visit_stack = [-1]
    vertices_status_list = [UNVISITED] * vertices_num
    vertices_status_list.insert(0, -1)
    vertices_d_time, vertices_f_time = ([0] * (vertices_num + 1) for _ in range(2))

    adj_matrix = generate_adj_matrix(vertices_info)
    # timing start from 1
    time = 1
    dfs_start()
    for k in range(vertices_num):
        print(k + 1, vertices_d_time[k + 1], vertices_f_time[k + 1])