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:
from sys import stdin
n = int(stdin.readline())
M = [0] + [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [0] + [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)
    print(*sndf[i][1:])

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
M = [None] + [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [None] + [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)
    print(*sndf[i][1:])

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
M = [None]
M += [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [None]
sndf += [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)
    print(*sndf[i][1:])

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
M = [None]
M += [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [None]
sndf += [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
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:
from sys import stdin
n = int(stdin.readline())
M = [None] + [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [None] + [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
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:
from sys import stdin
n = int(stdin.readline())
M = [list(map(int, stdin.readline().split()[2:])) for i in range(n)]
sndf = [[False, i] for i in range(1, n + 1)]
tt = 0
def dfs(u):
    global tt
    sndf[u][0] = True
    tt += 1
    sndf[u].append(tt)
    for v in M[u]:
        v -= 1
        if not sndf[v][0]:
            dfs(v)
    tt += 1
    sndf[u].append(tt)
for i in range(0, n):
    if not sndf[i][0]:
        dfs(i)
    print(*sndf[i][1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def DFS_stack(adj, start):
    n = len(adj)
    d = [0] * n
    f = [0] * n
    flag = [0] * n # 0:????¨????, 1:?¨??????????, 2:?¨??????????
    S = []
    time = 1

    S.append(start)
    flag[start] = 1
    d[start] = time
    time = time + 1
    
    while flag.count(2) != n: # ??¨????????????????????¢?´¢????????????????????§
        if len(S) != 0:
            u = S.pop()
            v = [i for i, x in enumerate(adj[u]) if (x == 1) and (flag[i] == 0)] 
            # v := ??£??\???????????????????????¢?´¢??????????????????
            if len(v) != 0:
                S.append(u)
                S.append(v[0])
                flag[v[0]] = 1
                d[v[0]] = time
                time = time + 1
            else:
            #??£??\??????????????¨????¨??????????
                flag[u] = 2
                f[u] = time
                time = time + 1

        else:
        	#??????????????????????????£?????´????????¢?´¢??????????????????????????¢?´¢????§?
            u = flag.index(0)
            S.append(u)
            flag[u] = 1
            d[u] = time
            time = time + 1            

    return d, f    

def DFS(adj, start):
    
    n = len(adj)
    d = [0] * n
    f = [0] * n
    flag = [0] * n
    time = 1
    
    def DFS_recursive(u, time):
        #print(u, flag)
        flag[u] = 1
        d[u] = time
        time = time + 1
        v = [i for i, x in enumerate(adj[u]) if x == 1]
        for i in v:
            if flag[i] == 0:
                time = DFS_recursive(i, time)
        flag[u] = 2
        f[u] = time
        time = time + 1
        return time
        
    time = DFS_recursive(start, time)
    for i in range(n):
        if flag[i] == 0:
           time =  DFS_recursive(i, time)
    
    return d, f



def main():
    
    n = int(input())
    adj = [[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        tmp = list(map(int, input().split()))
        u = tmp[0]
        u = u -1
        k = tmp[1]
        v = tmp[2:]
        for j in range(k):
            adj[u][v[j]-1] = 1
            
    #d, f = DFS_stack(adj, 0)
    d, f = DFS(adj, 0)
    for i in range(n):
        print(i+1, d[i], f[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def dfs(u):
    global time
    color[u] = "GRAY"
    time += 1
    d[u] = time
    for v in range(n):
        if M[u][v] and color[v] == "WHITE":
            dfs(v)
    color[u] = "BLACK"
    time += 1
    f[u] = time


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    color = ["WHITE"] * n
    time = 0
    d = [-1] * n
    f = [-1] * n
    M = [[0] * n for i in range(n)]
    for inp in sys.stdin.readlines():
        inp = list(map(int, inp.split()))
        for i in inp[2:]:
            M[inp[0]-1][i-1] = 1
    for i in range(n):
        if d[i] == -1:
            dfs(i)
    for i in range(n):
        print(i+1, d[i], f[i])

Submission status: Accepted

Solution code:
# coding: utf-8
def depth(i, adj, Dep, Arr, times):
    if Dep[i-1]:
        return times
    Dep[i-1]=times
    times+=1
    # t=[depth(j, adj, Dep, f, times) j in adj[i-1]]
    for j in adj[i-1]:
        times=depth(j, adj, Dep, Arr, times)
    Arr[i - 1]=times
    times+=1
    return times


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

d,f=[0]*n,[0]*n

t=1

dlist=[i for i in range(n) if d[i]==0]

for i in dlist:
    t = depth(i + 1, adj, d, f, t)

for i, df in enumerate(zip(d, f)):
    print(i + 1, *df)

Submission status: Accepted

Solution code:
import sys

#sys.setrecursionlimit(100000)
u=[]
k=[]
v=[]

time = 0

n=int(sys.stdin.readline().strip())
yattayatu=[False for i in range(n)]

s=[0 for i in range(n)]
f=[0 for i in range(n)]

for i in range(n):
	inp = sys.stdin.readline().strip().split(" ")
	inp = list(map(lambda x: int(x), inp))
	u.append(inp[0])
	k.append(inp[1])
	v.append(inp[2:])


def func(nodeid):
	global time
	if(yattayatu[nodeid-1]==True):
		return
	yattayatu[nodeid-1]=True
	time += 1
	s[nodeid-1] = time
	for i in range(k[nodeid-1]):
		func(v[nodeid-1][i])
	time +=1
	f[nodeid-1]=time
	return

for i in range(n):
	func(i+1)

for i in range(n):
	print(str(i+1)+" "+str(s[i])+" "+str(f[i]))

Submission status: Accepted

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]) - 1 for i in range(2, len(array))])

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

while True:
    if len(stack) == 0:
        ll = filter(lambda x: x not in searched_list, range(0, d_num))
        if len(ll) == 0:
            break
        stack.append(ll[0])
        result[ll[0]].append(t)
        searched_list.append(ll[0])
    else:
        node = stack[-1]
        children = filter(lambda x: x not in searched_list, graph_list[node])
        if len(children) != 0:
            next_node = children[0]
            stack.append(next_node)
            result[next_node].append(t)
            searched_list.append(next_node)
        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]) + " " + str(result[i][1])

Submission status: Accepted

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

stmp = 1
for v in range(1, d_num+1):
    if v not in visited: stmp = dfs(v, stmp)

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

Submission status: Accepted

Solution code:
from collections import OrderedDict

class Stack():
    def __init__(self):
        self.el = []
    def add(self, el):
        self.el.append(el)
    def pop(self):
        return self.el.pop()
    def top(self):
        return self.el[-1]
    def isEmpty(self):
        if self.el:
            return False
        return True

class Node():
    def __init__(self, id, edge=[], flag=0, discover=0, finish=0):
        self.id = id
        self.edge = edge
        self.flag = flag
        self.discover = discover
        self.finish = finish
    def show(self):
        print self.id, self.discover, self.finish
        
def notVisited(dic):
    for i in dic.keys():
        if dic[i].flag != 2:
            return i
    return None
        
n = int(raw_input())
dic = {}
for i in range(n):
    tmp = map(int, raw_input().split())
    if tmp[1] > 0:
        dic[tmp[0]] = Node(tmp[0], tmp[2:])
    else:
        dic[tmp[0]] = Node(tmp[0])
dic = OrderedDict(dic)

start = 1
time = 1
st = Stack()
dic[start].flag = 1
dic[start].discover = time
st.add(dic[start])

while not st.isEmpty():
    time += 1
    u = st.top()
    v = u.edge
    if v:
        for i in range(len(v)):
            if dic[v[i]].flag == 0:
                dic[v[i]].flag = 1
                dic[v[i]].discover = time
                if i != len(v)-1:
                    dic[u.id].edge = u.edge[i+1:]
                else:
                    dic[u.id].edge = []
                st.add(dic[v[i]])
                break
        else:
            st.pop()
            dic[u.id].flag = 2
            dic[u.id].finish = time
    else:
        st.pop()    
        dic[u.id].flag = 2
        dic[u.id].finish = time
    if st.isEmpty() and notVisited(dic):
        new = notVisited(dic)
        dic[new].flag = 1
        time += 1
        dic[new].discover = time
        st.add(dic[new])
for i in dic.keys():
    dic[i].show()

Submission status: Accepted

Solution code:
N = int(input())
Adj = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    u = list(map(int, input().split()))
    if u[1] > 0:
        for k in u[2: 2+u[1]]:
            Adj[u[0] - 1][k - 1] = 1
            
            
color = [0] * N #1: visited, 0: not visited, 2: completed
s = [0] * N # start
f = [0] * N # finish

time = 0

def DFS(u):
    global time
    color[u-1] = 1
    time += 1
    s[u-1] = time
    
    for i in range(1, N+1):
        if Adj[u-1][i-1] == 1 and color[i-1] == 0:
            DFS(i)
            
    color[u-1] = 2
    time += 1
    f[u-1] = time

for i in range(1, N+1):
    if color[i-1] == 0:
        DFS(i)
        
for i in range(N):
    print('{} {} {}'.format(i+1, s[i], f[i]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)
N = int(input())
adj = [[0]*N for _ in range(N)]
searched = {n: 0 for n in range(N)}
edge = {}

for n in range(N):
    inp = list(map(int, input().split()))
    edge[n] = inp[1]
    for i in inp[2:]:
        adj[inp[0]-1][i-1] = 1

time = 1
stack = []
unsearch = set(range(N))
uncomplete = set(range(N))
result = {n:{"found": 0, "finish": 0} for n in range(N)}

def DFS(i):
    global time
    global unsearch
    
    itr = sorted(unsearch)
    
    for j in itr:
        if adj[i][j] == 1 and j in unsearch:
            result[j]["found"] = time
            time += 1
            unsearch.remove(j)
            DFS(j)
    result[i]["finish"] = time
    time += 1
    
while len(unsearch):
    i = min(unsearch)
    unsearch.remove(i)
    result[i]["found"] = time
    time += 1
    DFS(i)

for n in range(N):
    print("{} {} {}".format(n+1, result[n]["found"], result[n]["finish"]))

Submission status: Accepted

Solution code:
n = int(input())
graph = {}
ans = []
np = set(range(1,n+1))
for i in range(n):
    t = list(map(int, input().split()))
    v = t[0]
    k = t[1]
    graph[v] = [t[i+2] for i in range(k)]
    np=np - set(graph[v])
    ans.append([v,None,None])

class Time:
    def __init__(self):
        self.time = 0
    def getTime(self):
        self.time += 1
        return self.time

t = Time()

visited = set()
def dfs(graph, target):
    visited.add(target)
    # ???????????????????¨????
    if ans[target - 1][1] is None:
        ans[target - 1][1] = t.getTime()
    if graph[target] == []:
        if ans[target - 1][2] is None:
            ans[target - 1][2] = t.getTime()        
        return
    for v in sorted(graph[target]):
        # # ???????????????????¨????
        if v not in visited:        
            if ans[v - 1][1] is None:
                ans[v - 1][1] = t.getTime()        
            visited.add(target)
            dfs(graph,v)
    if ans[target - 1][2] is None:
        ans[target - 1][2] = t.getTime()

if np == set():
    np = [1]
for v in sorted(list(np)):
    dfs(graph,v)
for row in ans:
    print(*row)

Submission status: Accepted

Solution code:
def srch(u, cnt, Dst, Fst, Lst):
    S = [u]
    Fst[u] = cnt
    while(len(S) > 0):
        cnt += 1
        u = S.pop()
        if Dst[u] is not None and len(Dst[u]) > 0:
            while(len(Dst[u])):
                u1 = Dst[u].pop()
                if Fst[u1] == 0:
                    S.append(u)
                    S.append(u1)
                    Fst[u1] = cnt
                    break
                else:
                    Lst[u] = cnt
        else:
            Lst[u] = cnt
    return cnt + 1

def main():
    num = int(input())
    Dst = [None for i in range(num + 1)]
    Fst = [0] * (num + 1)
    Lst = Fst[:]

    for n in range(1, num+1):
        a = list(map(int,input().split()))
        u = a[0]
        if a[1] > 0:
            Dst[u] = a[2:]
            Dst[u].reverse()

    cnt = 1
    for i in range(1,num):
        if Fst[i] == 0:
            cnt = srch(i, cnt, Dst, Fst, Lst)

    for n in range(1, num+1):
        print("{} {} {}".format(n,Fst[n],Lst[n]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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:
    j=2
    while t<N*2 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])
        r.pop(-1)
        p.pop(-1)
        if len(r)>0:
            i=r[-1]-1
        else:
            j=1
            while j<N and a[j]==1:
                j+=1
            if j<N:
                t+=1
                i=j-1
                r.append(j)
                p.append([j,t])
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: Accepted

Solution code:
# coding: utf-8
timestamp = 1

stack = []
indata = []
visit = []      #?¨?????¨????
visitTime = []  #?¨???????????¨??????¨
lastTimeStack = []      #?¨?????????????????¨??????¨


def inputdata():
    global      visit
    global      indata
    global      visitTime

    n = int(input().rstrip())

    for i in range(n):
        visit.append(True)
        visitTime.append([0, 0])

        lst = [int(i) for i in input().rstrip().split(" ")]
        k = lst[1]
        v = []
        for j in range(k):
            v.append(lst[2 + j] - 1)
        indata.append(v)

def procV(n):
    global lastTimeStack
    global timestamp
    global visit
    global stack

    if visit[n]:
        stack.append(n)
        lastTimeStack.append(n)
        visitTime[n][0] = timestamp
        timestamp += 1
        visit[n] = False
    else:
        if visitTime[n][1] == 0:
            visitTime[n][1] = timestamp
            timestamp += 1

"""
main
"""
inputdata()
stack.append(0)             #?????????????´????push??????

while True:
    if len(stack) == 0:
        isNotVisit = True
        n = 0
        for i in visit:
            if i:
                isNotVisit = False
                stack.append(n)
                break
            n += 1
        if isNotVisit:
            break

    n = stack.pop()         #??????????????????pop??????
    procV(n)                #pop????????????????????????????????????

    #???????????¢???
    for i in reversed(indata[n]):
        if visit[i]:
            hasNotChildAdd = False
            stack.append(i)

i = 1
for val in visitTime:
    li = [i, val[0], val[1]]
    print(' '.join(map(str, li)))
    i += 1

Submission status: Accepted

Solution code:
def main():
    n = input()
    A = []
    s = []
    B = [[0,0] for i in xrange(n)]
    for i in xrange(n):
        A.append(map(int,raw_input().split()))

    color = [-1]*n
    d = [0]*n
    f = [0]*n
    t = 0
    
    for i in xrange(n):
        if color[i] == -1:
            t = dfs(i,t,color,d,f,A,n)

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


def dfs(u,t,color,d,f,A,n):
    t += 1
    color[u] = 0
    d[u] = t
    for i in A[u][2:]:
        if (color[i-1] == -1):
            t = dfs(i-1,t,color,d,f,A,n)
    color[u] = 1
    t += 1
    f[u] = t
    return t

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
color = [0] * N
d = [0] * N
f = [0] * N
nt = [0] * N
m = [[0] * N for i in range(N)]
S = []
tt = 0

def next(u):
    global nt
    w = nt[u]
    for v in range(w, N):
        nt[u] = v + 1
        if( m[u][v] ):
            return v
    return -1

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

    while( len(S) != 0 ):
        u = S[-1]

        v = next(u)
        if ( v != -1 ):
            if ( color[v] == 0 ):
                color[v] = 1
                tt += 1
                d[v] = tt
                S.append(v)
        else:
            S.pop()
            color[u] = 2
            tt += 1
            f[u] = tt
        
def dfs():
    global color
    for u in range(N):
        if( color[u] == 0 ):
            dfs_visit(u)

if __name__ == '__main__':

    for i in range(N):
        v = map(int, raw_input().split())
        for j in v[2:]:
            m[i][j-1] = 1
    
    dfs()

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

Submission status: Accepted

Solution code:
n = int(input())
G = []
checked = [False for i in range(n + 1)]
d = [0 for i in range(n + 1)]
f = [0 for i in range(n + 1)]
G.append([])
for i in range(n):
    u, k, *v = map(int, input().split())
    G.append(v)

timestamp = 1

def dfs(id):
    global timestamp

    checked[id] = True
    d[id] = timestamp
    timestamp += 1
    for v in G[id]:
        if not checked[v]:
            dfs(v)
    f[id] = timestamp
    timestamp += 1

for id in range(1, n + 1):
    if not checked[id]:
        dfs(id)

for i in range(1, n + 1):
    print("{0} {1} {2}".format(i, d[i], f[i]))

Submission status: Accepted

Solution code:
n = int(input())
graph = [list(map(int, input().split())) for i in range(n)]

v_color = ["WHITE"] * (n+1) # WHITE:????¨???????GRAY:?¨??????????BLACK:??¢?´¢??????
d = [0] * (n+1)
f = [0] * (n+1)
stack = []
time = 0
def DFS(u):
    global time
    stack.append(u)

    while stack != []:
        u = stack[-1]
        time += 1
        
        v_color[u] = "GRAY"
        if d[u] == 0:
            d[u] = time
        
        for Next in graph[u-1][2:]:
            if v_color[Next] == "WHITE":
                stack.append(Next)
                break
        
        else:
            v_color[u] = "BLACK"
            f[u] = time +1
            stack.pop()
        
for i in range(1,n+1):
    if v_color[i] == "WHITE":
        DFS(i)
        time += 1
    
for i in range(1,n+1):
    print(i,d[i],f[i])

Submission status: Accepted

Solution code:
n = int(input())
A = [[False for _ in range(n)] for _ in range(n)]
for _ in range(n):
    tmp = list(map(int, input().split()))
    for i in range(tmp[1]):
        A[tmp[0]-1][tmp[i+2]-1] = True

WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for _ in range(n)]
d = [0 for _ in range(n)]
f = [0 for _ in range(n)]
time = 1

def dfs(u):
    global dfs_color, d, f, time
    color[u] = GRAY
    d[u] += time
    time += 1
    for v in range(n):
        if A[u][v]:
            if color[v] == WHITE:
                dfs(v)
        else:
            continue
    color[u] = BLACK
    f[u] = time
    time += 1 

for u in range(n):
    if color[u] == WHITE:
        dfs(u)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(here, connect, visited, answer):
    global time
    answer[here][1] = time
    time += 1
    visited[here] = 1
    for c in connect[here]:
        if not visited[c]:
            dfs(c, connect, visited, answer)
    answer[here][2] = time
    time += 1

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num):
    inp = [int(n) - 1 for n in input().split(" ")]
    connect[inp[0]].extend(sorted(inp[2:]))
answer = [[n + 1 for m in range(3)] for n in range(v_num)]
time = 1
visited = [0 for n in range(v_num)]
for i in range(v_num):
    if not visited[i]:
        dfs(i, connect, visited, answer)
for v in range(v_num):
    print(*answer[v])

Submission status: Accepted

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)]
v = []

for i in range(n):
    g.append(list(map(int, input().split())))


for i in range(1, n + 1):
    if i in v:
        continue
    dfs(g,i,r,v)
    j += 1

for i in range(1,n+1):
    print(*r[i])

Submission status: Accepted

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

edge=[[0 for i2 in range(n)]for i1 in range(n)]

#??£??\???????????????

for i in range(n):
    for j in range(adj[i][1]):
        edge[i][adj[i][j+2]-1]=1


time=1
discover=[0 for i in range(n)]
final=[0 for i in range(n)]
stack=[]

def dfs(id,time):
    for i in range(n):
        c=0
        if edge[id][i]==1 and discover[i]==0:
            stack.append(id)
            discover[i]=time
            c+=1
            #print(discover,final,i,stack)
            dfs(i,time+1)
        else:
            pass
    if c==0:
        if len(stack)>0:
            if final[id]==0:
                final[id] = time
                #print("back",discover,final,id,stack)
                dfs(stack.pop(), time + 1)
            else:
                #print("back", discover, final, id, stack)
                dfs(stack.pop(),time)

discover[0]=time
stack.append(0)
dfs(0,time+1)


for i in range(n):
    if discover[i]==0:
        discover[i]=final[0]+1
        stack.append(i)
        dfs(i,final[0]+2)
        break

for i in range(n):
    print(i+1,discover[i],final[i])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

n = int(input())
M = [[False for i in range(n)] for j in range(n)]
WHITE = 0
GRAY = 1
BLACK = 2
color = [WHITE for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
t = 1
for i in range(n):
        a = list(map(int, input().split()))
        for j in range(a[1]):
            M[a[0] - 1][a[j + 2] - 1] = True
for u in range(n):
    if color[u] == WHITE:
        dfs_visit(u)
for u in range(n):
    print(str(u + 1), str(d[u]), str(f[u]), sep = " ")

Submission status: Accepted

Solution code:
n = int(input())
a = [[0]*n for i in range(n)]
  
for i in range(n):
    v = list(map(int, input().split()))
    u = v[0]
    k = v[1]
    for j in range(k):
        a[u - 1][v[2 + j] - 1] = 1

d = [0] * n
f = [0] * n
isDiscovered = [False] * n
time_stamp = 0

def dfs(x):
    global time_stamp
    isDiscovered [x] = True
    time_stamp = time_stamp + 1
    d[x] = time_stamp
    for i in range(n):
        if a[x][i] == 1 and isDiscovered[i] == False:
            dfs(i)
    time_stamp = time_stamp + 1
    f[x] = time_stamp

for i in range(n):
    if isDiscovered[i] == False:
        dfs(i)

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

Submission status: Accepted

Solution code:
n = int(input())
a = [[False]*n for i in range(n)]
  
for i in range(n):
    v = list(map(int, input().split()))
    u = v[0]
    k = v[1]
    for j in range(k):
        a[u - 1][v[2 + j] - 1] = True

d = [0] * n
f = [0] * n
isDiscovered = [False] * n
time_stamp = 0

def dfs(x):
    global time_stamp
    isDiscovered [x] = True
    time_stamp = time_stamp + 1
    d[x] = time_stamp
    for i in range(n):
        if a[x][i]and not isDiscovered[i]:
            dfs(i)
    time_stamp = time_stamp + 1
    f[x] = time_stamp

for i in range(n):
    if not isDiscovered[i]:
        dfs(i)

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

Submission status: Accepted

Solution code:
n = int(input())
a = [[] for i in range(n)]

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

d = [0] * n
f = [0] * n
isDiscovered = [False] * n
time_stamp = 0

def dfs(x):
    global time_stamp
    isDiscovered [x] = True
    time_stamp += 1
    d[x] = time_stamp
    for i in a[x]:
        if not isDiscovered[i]:
            dfs(i)
    time_stamp += 1
    f[x] = time_stamp

for i in range(n):
    if not isDiscovered[i]:
        dfs(i)

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

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)
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:
n=int(input())
d=[0 for _ in range(n+1)]
f=[0 for _ in range(n+1)]
G=[]
G.append([])
for i in range(n):
    u,k,*v=map(int,input().split())
    G.append(v)

checked=[False for _ in range(n+1)]
timestamp=1

def dfs(id):
    global timestamp
    d[id]=timestamp
    checked[id]=True
    timestamp+=1
    for v in G[id]:
        if not checked[v]:
            dfs(v)
    f[id]=timestamp
    timestamp+=1

for id in range(1,n+1):
    if not checked[id]:
        dfs(id)

for i in range(1,n+1):
    print("{0} {1} {2}".format(i,d[i],f[i]))