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: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and st[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if st[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and st[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if st[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if st[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = [0]
 
def DFS_v(u):
    color[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print u+1, d[u], f[u]
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] == 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print "%d %d %d" %(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] = 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print "%d %d %d" %(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 1 and color[v] == 0:
      DFS_v(v)
  color[u] = 2
  t += 1
  f[u] = t
 
def DFS():
  for u in range(n):
    if color[u] == 0:
        DFS_v(u)
  for u in range(n):
    print "%d %d %d" %(u+1, d[u], f[u])
     
for i in range(n):
  X = map(int, raw_input().split())
  for j in range(X[1]):
    M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [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)]
t = 0
 
def DFS_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 1 and color[v] == 0:
      DFS_v(v)
  color[u] = 2
  t += 1
  f[u] = t
 
def DFS():
  for u in range(n):
    if color[u] == 0:
        DFS_v(u)
  for u in range(n):
    print '%d %d %d' %(u+1, d[u], f[u])
     
for i in range(n):
  X = map(int, raw_input().split())
  for j in range(X[1]):
    M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    clo[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

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)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Submission status: Runtime Error

Solution code:
import sys
 
def dfs(i, t, l, a, b):
   t += 1
   a[i] = t
   for j in l[i]:
      if not a[j-1]:
         t = dfs(j-1, t, l, a, b)
   t += 1
   b[i] = t
   return t
 
 
n = input()
l=[]
for i in range(n):
   x = int(s) for s in sys.stdin.readline().split()[2:]
   l.append(x)
a = [0] * n
b = [0] * n
t = 0
for i in xrange(n):
   if not a[i]:
      tm = dfs(i, t, l, a, b)
 
for i in xrange(n):
   print i+1, a[i], b[i]

Submission status: Runtime Error

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)
    time[0] += 1
    f[s] = time[0]

def main():
    for s in range(n):
        if st[s] == 0:
            def_visit(s)
    for s in range(n):
        print(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
   
main()

Submission status: Runtime Error

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)
    time[0] += 1
    f[s] = time[0]

def main():
    for s in range(n):
        if st[s] == 0:
            def_visit(s)
    for s in range(n):
        print(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: Runtime Error

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'{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]):
        a[G[0]-1][g[2+j]-1] = 1

int main

Submission status: Runtime Error

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'{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]):
        a[g[0]-1][G[2+j]-1] = 1
 
main()

Submission status: Runtime Error

Solution code:
def depth(s, time):
    time += 1
    f[s] = 1
    d[s] = t
    for i in range(1, n+1):
        if G[s][i] == 1:
            if f[i] == 0:
                depth(i, time)
                t = f[i]
    f[s] = time + 1
 
n = int(raw_input())
G = [[0 for i in range(n+1)] for j in range(n+1)]
d = [0 for i in range(n+1)]
f = [0 for i in range(n+1)]
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+j]] = 1
 
flag = [0 for i in range(n+1)]
for i in range(1, n+1):
    if flag[i] == 0:
        depth(i, max(f))
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]) + " " + str(f[i]))

Submission status: Runtime Error

Solution code:
def depth(s, time):
    time += 1
    flag[s] = 1
    d[s] = t
    for i in range(1, n+1):
        if G[s][i] == 1:
            if flag[i] == 0:
                depth(i, time)
                t = f[i]
    f[s] = time + 1
 
n = int(raw_input())
G = [[0 for i in range(n+1)] for j in range(n+1)]
d = [0 for i in range(n+1)]
f = [0 for i in range(n+1)]
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+j]] = 1
 
flag = [0 for i in range(n+1)]
for i in range(1, n+1):
    if flag[i] == 0:
        depth(i, max(f))
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]) + " " + str(f[i]))

Submission status: Runtime Error

Solution code:
N     = 100

M     = [[0 for i in range(N)] for j in range(N)]
color = [0 for i in range(N)]
d     = [0 for i in range(N)]
f     = [0 for i in range(N)]
tt    = 0

###
def dfs_visit(u):
    color[u] = 1
    tt = tt + 1
    d[u] = tt

    for v in range(n):
        if M[u][v] == 0:
            continue
        if color[v] == 0:
            dfs_visit(v)
    color[u] = 2
    tt = tt + 1
    f[u] = tt

###
def dfs():
    for u in range(n):
        color[u] = 0
    tt = 0

    for u in range(n):
        if color[u] == 0:
            dfs_visit(u)

    for u in range(n):
        print "%d %d %d" %(u + 1, d[u], f[u])

### MAIN
n = input()

for i in range(n):
    for j in range(n):
        M[i][j] = 0

for i in range(n):
    Num = map(int, raw_input().split())
    u = Num[0]
    k = Num[1]
    u = u - 1
    for j in range(k):
        v = Num[j]
        v = v - 1
        M[u][v] = 1

dfs()

Submission status: Runtime Error

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


def d(u):
    global n
    if ts[u]:return
    n = n + 1
    ts[u]=[u+1,n]
    for i in c[u]:d(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):
     d(i)
     print " ".join(map(str,t[i]))

dfs()

Submission status: Runtime Error

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


def d(u):
    global n
    if ts[u]:return
    n = n + 1
    ts[u]=[u+1,n]
    for i in c[u]:d(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):
     d(i)
     print " ".join(map(str,ts[i]))

dfs()

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

Solution code:
def curserch(N,k,t,P,n):
    g = 0
    t = t+1
    P[k]["d"] = t
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            P[i]["f"] = g = curserch(N,i,t,P,n)
    if g !=0:
        return g+1
    else:
        return t+1

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)]
P[1]["f"] = curserch(A,1,0,P,n)
j=1
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"])

Submission status: Runtime Error

Solution code:
def curserch(N,k,t,P,n):
    g = 0
    t = t+1
    P[k]["d"] = t
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            P[i]["f"] = g = curserch(N,i,t,P,n)
    if g !=0:
        return g+1
    else:
        return t+1

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)]
P[1]["f"] = curserch(A,1,0,P,n)
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"])

Submission status: Runtime Error

Solution code:
def dfs(u, node_info, matrix):
    # ????????????????????¨??????????????????
    colors = [0] * len(matrix)
    detect_time = [0] * len(matrix)
    finished_time = [0] * len(matrix)
    time = 1
    stack = list()
    stack.append(u)
    colors[u] = 1
    detect_time[u] = time
    while len(stack):
        for i, val in enumerate(matrix[u]):
            if val == 1 and colors[i] == 0:
                time += 1
                stack.append(i)
                colors[i] = 1
                detect_time[i] = time
                u = i
                break
        else:
            time += 1
            e = stack.pop()
            colors[e] = 2
            finished_time[e] = time
            if len(stack):
                u = stack[-1]
    for i in range(len(matrix)):
        print('{} {} {}'.format(i + 1, detect_time[i], finished_time[i]))


if __name__ == '__main__':
    N = int(input())
    matrix = [[0] * N for _ in range(N)]
    color = [0] * N
    for i in matrix:
        node_info = [int(i) for i in input().split()]
        node_i = node_info[0] - 1
        if not node_info[1] == 0:
            for i in node_info[2:]:
                matrix[node_i][i - 1] = 1
    for line in matrix:
    dfs(0, None, matrix)

Submission status: Runtime Error

Solution code:
from collections import deque


def dfs(root):
    global time
    stack.append(root)
    color[root] = 'gray'
    arrive[root] = time
    time += 1

    while len(stack) > 0:
        node = stack[-1]
        for next in range(n):
            if adjMat[node][next] == 1:
                if color[next] == 'white':
                    color[next] = 'gray'
                    arrive[next] = time
                    time += 1
                    stack.append(next)
                    break
        # In case there in no adjacent node whose color is white
        color[node] = 'black'
        finish[node] = time
        time += 1
        stack.pop()


n = int(input())

adjMat = [[0] * n for _ in range(n)]
color = ['white'] * n
stack = deque()
arrive = [0] * n
finish = [0] * n
time = 1

for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        adjMat[i - 1][j - 1] = 1

for root in range(n):
    if color[root] = 'white':
        dfs(root)

for i in range(n):
    out = ''
    out += '{} {} {}'.format(i+1, arrive[i], finish[i])
    print(out)

Submission status: Runtime Error

Solution code:
def dfs_recursive(u):
    global time
    color[u] = 'gray'
    arrive[u] = time
    time += 1
    for v in range(n):
        if adjMat[u][v] == 1 and color[v] == 'white':
            dfs_recursive(v)
    color[u] = 'black'
    finish[u] = time
    time += 1


n = int(input())

adjMat = [[0] * n for _ in range(n)]
color = ['white'] * n
arrive = [0] * n
finish = [0] * n
time = 1

for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        adjMat[i - 1][j - 1] = 1

for root in range(n):
    if color[root] == 'white':
        dfs(root)


for i in range(n):
    out = ''
    out += '{} {} {}'.format(i + 1, arrive[i], finish[i])
    print(out)

Submission status: Runtime Error

Solution code:
import sys

d_num = int(sys.stdin.readline().strip())

graph_list = []

for _ in range(0, d_num):
    array = sys.stdin.readline().strip().split(" ")
    if len(array) > 2:
        graph_list.append([])
    else:
        graph_list.append([int(array[i]) for i in range(2, len(array))])

t = 1
result = [[] for _ in range(0, d_num)]
searched_list = []
stack = []

stack.append(0)
while sorted(searched_list) != range(0, d_num):
    if len(stack) == 0:
        stack.append(filter(lambda x: x not in searched_list, range(0, d_num))[0])
    node = stack[-1]
    searched_list.append(node)
    children = filter(lambda x: x not in searched_list, graph_list[node])
    if len(child) == 0:
        next_node = children[0]
        result[next_node].append(t)
    else:
        stack.pop()
        result[node].append(t)
    t += 1

s = ""

for i in range(0, len(result)):
    print str(i+1) + " " + str(result[i][0] + 1) + " " + str(result[i][1] + 1)

Submission status: Runtime Error

Solution code:
from sys import stdin

d_num = int(stdin.readline().strip())

graph = [[] for _ in range(d_num+1)]
for _ in range(d_num):
    u, k, *neighbors = map(int, stdin.readline().split())
    for v in neighbors:
        graph[u].append(v)

visited = set()
timestamps = [None for _ in range(d_num+1)]

def dfs(u, stmp):
    visited.add(u)
    entry = stmp

    stmp += 1
    for v in graph[u]:
        if v not in visited:
            stmp = dfs(v, stmp)

    timestamps[u] = entry, stmp
    return stmp+1

dfs(1, 1)

for num, (entry, leave) in enumerate(timestamps[1:], 1):
    print(num, entry, leave)

Submission status: Runtime Error

Solution code:
   #depth first
N=int(input())
V=[]
a=[0]
for i in range(N):
    V.append([int(i) for i in input().split()])
    w=V[i][2:]
    w.sort()
    V[i]=V[i][:2]+w
    a.append(0)
V=sorted(V,key=lambda x:x[0])
c=1
t=1
i=0
r=[1]
a[1]=1
p=[[1,t]]
q=[]
while t<N*2-1:
    j=2
    while t<N*2-1 and j-2<V[i][1] and V[i][1]>0 and a[V[i][j]]==1:
        j+=1
    t+=1
    if j-2<V[i][1]:
        a[V[i][j]]=1
        c+=1
        r.append(V[i][j])
        p.append([V[i][j],t])
        i=V[i][j]-1
    else:
        q.append(p[-1]+[t])
#end time immediately case?
        r.pop(-1)
        p.pop(-1)
        i=r[-1]-1
       # print(q)
q.append([1,1,N*2])
q=sorted(q,key=lambda x:x[0])
for i in range(N):
    for j in range(3):
        q[i][j]=str(q[i][j])
    print(" ".join(q[i]))

Submission status: Runtime Error

Solution code:
j = 1
def dfs(graph, start, result, visited=None):
    global j
    if visited == None:
        visited = []
    visited.append(start)
    result[start][1]  = j
    for next in graph[start][2:]:
        if next in visited:
            continue
        j += 1
        dfs(graph, next, result, visited)
    else:
        j += 1
        result[start][2] = j

n = int(input())
g = [[]]
r = [[i,0,0] for i in range(n + 1)]

for i in range(n):
    g.append(list(map(int, input().split())))
dfs(g,1,r)
for i in range(1:n+1)
    print(*r[i])

Submission status: Runtime Error

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]

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

def dfs():
    tt = 0
    for u in range(n):
        if (color[u] = WHITE):
            visit(u)
    for u in range(n):
        print(u+1, d[u], f[u], sep = " ", end ="\n")

n = int(input())
    for i in range(n):
        for j in range(n):
            M[i][j] = 0
for i in range(n):
    u, k = int(input())
    u -= 1
    for j in range(k):
        v = int(input())
        v -= 1
        M[u][v] = 1

dfs()

Submission status: Runtime Error

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1

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

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(u+1, d[u], f[u], sep = " ", end ="\n")

n = int(input())
M = [[[0] for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

Submission status: Runtime Error

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1

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

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

n = int(input())
M = [[[0] for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

Submission status: Runtime Error

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1

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

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for i in range(n):
    print(str(i+1), str(d[i]), str(f[i]), sep = " ")

n = int(input())
M = [[[0] for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

Submission status: Runtime Error

Solution code:
WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1

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

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

Submission status: Runtime Error

Solution code:

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1

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

for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")

Submission status: Runtime Error

Solution code:
def visit(u):
    global color, d, f, t
    color[u] = GRAY
    d[u] += t
    t += 1
    for v in range(n):
        if (M[u-1][v-1] == 0):
            continue
        if (color[v] == WHITE):
            visit(v)
    color[u] = BLACK
    f[u] = t
    t += 1

n = int(input())
M = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    temp = list(map(int, input().split()))
    for i in range(temp[1]):
        M[temp[0]-1][temp[i+2]-1] = 1

WHITE = 0
GRAY = 1
BLACK = 2
color, d, f = [WHITE for i in range(n)]
t = 1
for u in range(n):
    if (color[u] == WHITE):
        visit(u)
for u in range(n):
    print(str(u+1), str(d[u]), str(f[u]), sep = " ")