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: Wrong Answer

Solution code:
n=0
t=1
def adjacent_matrix():
    global n
    n=int(input())
    v=[]
    array=[]
    for i in range(n):
        zero=[0 for i in range(n)]
        a=list(map(int,input().split()))
        a=a[2:]
        for j in a:
            zero[j-1]=1
        array.append(zero)
    return array
def dfs(array,i,d,f):
    global t
    if i == n:
        return
    else:
        if(d[i] == 0):
            d[i] = t
            t += 1
            for (j,x) in enumerate(array[i]):
                if x == 1:
                    dfs(array,j,d,f)
            f[i] = t
            t += 1
    return dfs(array,i+1,d,f)


def main():
    array=adjacent_matrix()
    print()
    d=[0 for i in range(n)]
    f=[0 for i in range(n)]
    dfs(array,0,d,f)
    for i in range(n):
        print("{} {} {}".format(i+1,d[i],f[i]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[[0 for i in range(n)]for j in range(n)]
for i in range(n):
    v=list(input().split())
    for j in range(len(v)):
        v[j]=int(v[j])
    x=2
    for k in range(v[1]):
        a[i][v[x+k]-1]=1
#print(a)

stack=[]
v=[]
d=[0]*n
f=[0]*n
t=1

while len(v)<n:
    for i in range(n):
        if i+1 not in v:
            stack.append(i+1)
            d[i]=t
            break
        else: pass
        
    while len(stack)!=0:
        for i in range(n):
            if a[stack[-1]-1][i]==1 and stack[-1]-1!=i and i+1 not in v:
                stack.append(i+1)
                a[stack[-1]-1][i]==0
                t+=1
                d[i]=t
            elif i==n-1:
                t+=1
                f[stack[-1]-1]=t
                v.append(stack.pop())
            else: pass
            # print("stack ",stack)
            #print("v ",v)
#print("d=",d," f=",f)
for i in range(n):
    print(i+1,d[i],f[i])

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[[0 for i in range(n)] for j in range(n)]##静的確保 隣接行列
d=[0 for i in range(n)]##発見
f=[0 for i in range(n)]##完了
stack=[]##スタック
check=[]

for i in range(n):
    p=[int(x) for x in input().split()]
    
    for j in range(n):
        if j+1 in p[2:]:
            l[i][j]=1
##print("---隣接行列---")
##print(l)

time=1


while len(check)<n:
    for i in range(n):
        if i+1 not in check:
            stack+=[i+1]
            d[i]=time
            break
        else: pass

    while len(stack)!=0:
        ##print("----------while---------")
        for i in range(n):
            if l[stack[-1]-1][i]==1 and not i+1 in check and stack[-1]-1!=i:
                time+=1
                d[i]=time
                stack+=[i+1]

               ## print("stack:",stack)
               ## print("check:",check)
               ## print("d[",i,"]:",d[i])
                break
            elif i==n-1:
##最深    
                check+=[stack[-1]]
                time+=1
                f[stack.pop()-1]=time

               ## print("f[",i,"]:",f[i])
               ## print("check:",check)
    time+=1

Submission status: Wrong Answer

Solution code:
time=1
num=0
n=int(input())

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

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

def dfs(q,num):
	global d,f,time
	d[num]=time
	for nx in q[num]:
		if d[nx]==0:
			time+=1
			dfs(q,nx)
	time+=1
	f[num]=time
	

dfs(A,num)

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

Submission status: Wrong Answer

Solution code:
time=1
n=int(input())

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

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

def dfs(q,num):
	global d,f,time
	d[num]=time
	for nx in q[num]:
		if d[nx]==0:
			time+=1
			dfs(q,nx)
	time+=1
	f[num]=time
	
for i in range(n):
	if d[i]==0:#unvisit
		dfs(A,i)

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

Submission status: Wrong Answer

Solution code:
def h(G,G1,d,f,c,tmp,tmp1,n):
    if c[0]==2:
        f[0]=f[tmp]+1
        return 0
    cnt=0
    for i in range(n):
        if G1[tmp1][i]==1:
            if c[i]==0:
                d[i]=d[tmp1]+1
                c[i]+=1
                tmp=tmp1
                tmp1=i
                G1[tmp][i]=0
                h(G,G1,d,f,c,tmp,tmp1,n)

        else:
            cnt+=1
            if cnt==n:
                if c[tmp1]==1:
                    d[tmp1]=d[tmp]+1
                    c[tmp1]+=1
                    f[tmp1]=d[tmp1]+1
                    tmp=tmp1
                    for j in range(n):
                        if G[j][tmp]==1:
                            tmp1=j
                    G1[j][tmp1]=0
                    c[tmp1]+=1
                    h(G,G1,d,f,c,tmp,tmp1,n)
                elif c[tmp1]==2:
                    f[tmp1]=f[tmp]+1
                    tmp=tmp1
                    for j in range(n):
                        if G[j][tmp]==1:
                           tmp1=j
                           G1[j][tmp]=0
                    c[tmp1]+=1
                    h(G,G1,d,f,c,tmp,tmp1,n)
n=int(input())
d=[1 for i in range(n)]
f=[0 for i in range(n)]
c=[0 for i in range(n)]
G=[[0 for i in range(n)]for j in range(n)]
G1=[[0 for i in range(n)]for j in range(n)]
u=[0 for i in range(n)]
for i in range(n):
    A=input().split()
    u[i]=int(A[0])
    k=int(A[1])
    for j in range(k):
        x=int(A[j+2])-1
        G[i][x]=1
        G1[i][x]=1

d[0]=1
c[0]+=1
for i in range(n):
    if G[0][i]==1:
        d[i]=d[0]+1
        c[i]+=1
        tmp=0
        tmp1=i
        G1[0][i]=0
        break
h(G,G1,d,f,c,tmp,tmp1,n)
for i in range(n):
    print(i+1,d[i],f[i])

Submission status: Wrong Answer

Solution code:
#coding:utf-8

n = int(input())
c = ["white" for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
S = []
class DFS:
    def __init__(self, key, color="white",nex=None):
        self.color = color
        self.nex = nex
        self.key = key

objList = [DFS(i+1) for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    times = data[1]
    obj = objList[i]
    for j in range(times):
        index = data[2+j] - 1
        nextobj = DFS(index+1)
        obj.nex = nextobj
        obj = obj.nex

S.append(1)
obj = objList[0]
obj.color = "gray"
d[0] = 1
f[0] = 1
c[0] = "gray"

time = 1
while S != []:
    index = S[-1] - 1
    u = objList[index]
    v = u.nex

    time += 1
    if v != None and c[v.key - 1] == "white":
        objList[index] = v
        index = v.key - 1
        v = objList[index]
        c[v.key-1] = "gray"
        d[index] = time
        S.append(v.key)
        
    else:
        S.pop()
        c[u.key-1] = "black"
        f[index] = time

k = 1
for i,j in zip(d,f):
    print(k,i,j)
    k += 1

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from copy import deepcopy

n = int(input())
c = ["white" for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
S = []
class DFS:
    def __init__(self, key, color="white",nex=None):
        self.color = color
        self.nex = nex
        self.key = key

objListCopy = [DFS(i+1) for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    times = data[1]
    obj = objListCopy[i]
    for j in range(times):
        index = data[2+j] - 1
        nextobj = DFS(index+1)
        obj.nex = nextobj
        obj = obj.nex


time = 1
objList = objListCopy[:]
def check(first,time):
    obj = objList[first]
    c[first] = "gray"
    d[first] = time
    f[first] = time
    S.append(first+1)
    
    while S != []:
        index = S[-1] - 1
        u = objList[index]
        v = u.nex
        
        time += 1
        if v != None and c[v.key - 1] == "white":
            objList[index] = v
            index = v.key - 1
            v = objList[index]
            c[v.key-1] = "gray"
            d[index] = time
            S.append(v.key)

        elif v != None and c[v.key - 1] == "black" and v.nex != None:
            objList[index] = v
            time -= 1
            
        else:
            S.pop()
            c[u.key-1] = "black"
            f[index] = time
    return time


for i in range(n):
    if f[i] == 0:
        objList = deepcopy(objListCopy)
        time = check(i,time) + 1
        

k = 1
for i,j in zip(d,f):
    print(k,i,j)
    k += 1

Submission status: Wrong Answer

Solution code:
import sys

global stamp, counter
stamp = {}
counter=0

def dfs(key, GRAPH):
    global stamp, counter
    if stamp[key][0]==0:
        counter += 1
        stamp[key][0] = counter
    for e in GRAPH[key]:
        try:
            if stamp[e][0] == 0:
                dfs(e, GRAPH)
        except:
            pass
    counter += 1
    stamp[key][1] = counter
    return

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    key = seq[0]
    if key != 0:
        x[key] = seq[2:]
    else:
        x[key]=[]
    stamp[key]=[0,0]

dfs(x.keys()[0],x)

for e in x.keys():
    print e, stamp[e][0],stamp[e][1]

Submission status: Wrong Answer

Solution code:
import sys

global stamp, counter
stamp = {}
counter=0

def dfs(key, GRAPH):
    print "key: ",key
    global stamp, counter
    if stamp[key][0]==0:
        counter += 1
        stamp[key][0] = counter
    elif stamp[key][1] !=0:
        return

    for e in GRAPH[key]:
        try:
            if stamp[e][0] == 0:
                dfs(e, GRAPH)
        except:
            pass
    counter += 1
    stamp[key][1] = counter
    return

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    key = seq[0]
    if key != 0:
        x[key] = seq[2:]
    else:
        x[key]=[]
    stamp[key]=[0,0]
print x
for e in x.keys():
    dfs(e, x)

for e in x.keys():
    print e, stamp[e][0],stamp[e][1]

Submission status: Wrong Answer

Solution code:
import sys

global stamp, counter
stamp = {}
counter=0

def dfs(key, GRAPH):
    global stamp, counter
    if stamp[key][0]==0:
        counter += 1
        stamp[key][0] = counter
    elif stamp[key][1] !=0:
        return

    for e in GRAPH[key]:
        try:
            if stamp[e][0] == 0:
                dfs(e, GRAPH)
        except:
            pass
    counter += 1
    stamp[key][1] = counter
    return

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    key = seq[0]
    if key != 0:
        x[key] = seq[2:]
    else:
        x[key]=[]
    stamp[key]=[0,0]
print x
for e in x.keys():
    dfs(e, x)

for e in x.keys():
    print e, stamp[e][0],stamp[e][1]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


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(stdin.readline())

    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()[2:]])

    d = [0] * num
    f = [0] * num
    walk(0, 0, L, d, f)

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


main()

Submission status: Time Limit Exceeded

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 = 1, 0
stack = []
d[current] = time
while 0 in f:
    if not stack:
        stack.append(0)
    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: Time Limit Exceeded

Solution code:
n=int(input())

l=[[0 for i in range(n)] for j in range(n)]##静的確保 隣接行列
d=[0 for i in range(n)]##発見
f=[0 for i in range(n)]##完了
stack=[]##スタック
check=[]

for i in range(n):
    p=[int(x) for x in input().split()]
    
    for j in range(n):
        if j+1 in p[2:]:
            l[i][j]=1
##print("---隣接行列---")
##print(l)

time=1


while len(check)<n:
    for i in range(n):
        if i+1 not in check:
            stack+=[i+1]
            d[i]=time
            break
        else: pass

    while len(stack)!=0:
        ##print("----------while---------")
        for i in range(n):
            if l[stack[-1]-1][i]==1 and not i+1 in check and stack[-1]-1!=i:
                time+=1
                d[i]=time
                stack+=[i+1]

               ## print("stack:",stack)
               ## print("check:",check)
               ## print("d[",i,"]:",d[i])
                break
            elif i==n-1:
##最深    
                check+=[stack[-1]]
                time+=1
                f[stack.pop()-1]=time

               ## print("f[",i,"]:",f[i])
               ## print("check:",check)
    time+=1


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

Submission status: Time Limit Exceeded

Solution code:

#kadai11b Depth First Search

n=int(input())
t=1
a=[[0 for i in range(n)]for j in range(n)]
t1=[0 for i in range(n)]
t2=[0 for i in range(n)]
s=[]
c=[]
s.append(0)
t1[0]=t
t+=1
for i in range(n):
    p=[int(x) for x in input().split()]
    for j in range(n):
        if j+1 in p[2:]:
            a[i][j]=1

i=0
while len(c)!=n:
    if 1 not in a[i][0:]:
        if i not in c:
            t2[i]=t
            t+=1
            c.append(i)
            del s[-1]
            if len(s)>0:
                i=s[-1]
    for j in range(n):
        if a[i][j]==1:
            a[i][j]=0
            if j not in c:
                s.append(j)
                i=j
                t1[i]=t
                t+=1
            break

for i in range(n):
    print(i+1,t1[i],t2[i])

"""実行結果
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0
1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6
"""

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t=1
a=[[0 for i in range(n)]for j in range(n)]
t1=[0 for i in range(n)]
t2=[0 for i in range(n)]
s=[]
c=[]
s.append(0)
t1[0]=t
t+=1
for i in range(n):
    p=[int(x) for x in input().split()]
    for j in range(n):
        if j+1 in p[2:]:
            a[i][j]=1

i=0
while len(c)!=n:
    if 1 not in a[i][0:]:
        if i not in c:
            t2[i]=t
            t+=1
            c.append(i)
            del s[-1]
            if len(s)>0:
                i=s[-1]
    for j in range(n):
        if a[i][j]==1:
            a[i][j]=0
            if j not in c:
                s.append(j)
                i=j
                t1[i]=t
                t+=1
            break

for i in range(n):
    print(i+1,t1[i],t2[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  8 10:56:33 2018

@author: maezawa
"""
n = int(input())
adj = [[] for _ in range(n)]
d = [0 for _ in range(n)]
f = [0 for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(k):
        adj[u-1].append(ain[i+2]-1)
    adj[u-1].sort()
    #print(*adj[u-1])

t = 1

for j in range(n):
    if d[j] == 0:
        stack = [j]

    while stack:
        #print(stack)
        current = stack[-1]
        if d[current] == 0:
            d[current] = t
            t += 1
        flag = 0
        for k in adj[current]:
            if d[k] == 0:
                stack.append(k)
                flag = 1
                break
        if flag == 0:
            f[current] = t
            t += 1
            stack.pop()

    #print('current = {}, t = {}'.format(current, t))
    #print('stack', *stack)

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

Submission status: Accepted

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


class Graph:
    def __init__(self, n, adj_matrix):
        self.n = n
        self.adj_matrix = adj_matrix

    def show(self):
        for _ in self.adj_matrix:
            print(*_)

    def dfs(self):
        self.states = [2] * self.n
        self.d = [None] * self.n
        self.f = [None] * self.n
        self.time = 0

        for u in range(self.n):
            if self.states[u] == 2:
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.states[u] = 1
        self.time += 1
        self.d[u] = self.time

        for v, edge in enumerate(self.adj_matrix[u]):
            if edge and self.states[v] == 2:
                self.dfs_visit(v)

        self.states[u] = 0
        self.time += 1
        self.f[u] = self.time

    def show_dfs(self, start=0):
        self.dfs()
        for i, (d, f) in enumerate(zip(self.d, self.f)):
            print(i + 1, d, f)


if __name__ == '__main__':
    n = int(input())
    adj_matrix = [[0] * n for i in range(n)]
    for i in range(n):
        for v in input().split()[2:]:
            adj_matrix[i][int(v) - 1] = 1

    g = Graph(n, adj_matrix)
    g.show_dfs()

Submission status: Accepted

Solution code:
n = int(input())
graph = [[0 for i in range(n)] for j in range(n)]
d = [0] * n
f = [0] * n
g = [0] * n

time = 0

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

def search(i):
    global time
    time = time + 1
    d[i] = time
    g[i] = 1
    for j in range(n):
        if (graph[i][j] == 1) & (g[j] == 0):
            search(j)
    time = time + 1
    f[i] = time

for i in range(n):
    if g[i] == 0:
        search(i)
[print(i+1, d[i], f[i]) for i in range(n)]

Submission status: Accepted

Solution code:
def dfs(n):
    global t
    S[n] = t
    DP[n]=1
    for i in A[n][2:]:
        if not DP[i]:
            t += 1
            dfs(i)
    t += 1
    F[n] = t
n = int(input())
A = [0]*(n+1)
S = [0]*(n+1)
F = [0]*(n+1)
DP = [0]*(n+1)
for i in range(n):
    A[i+1] = [int(i) for i in input().split()]
t = 0
for i in range(1,n+1):
    if not DP[i]:
        t+=1
        dfs(i)
for i in range(1,n+1):
    tmp = "{} {} {}".format(i,S[i],F[i])
    print(tmp)

Submission status: Accepted

Solution code:
def dfs():
    tt = 0
    for u in range(N):
        if colors[u] == WHITE:
            tt = dfs_visit(u, tt)

def dfs_visit(u, tt):
    tt += 1
    colors[u] = GLAY
    d[u] = tt
    for v in range(N):
        if adjacency_list[u][v] == 1 and colors[v] == WHITE:
            tt = dfs_visit(v, tt)
    tt += 1
    colors[u] = BLACK
    f[u] = tt
    return tt


N = int(input())
adjacency_list = [[0 for j in range(N)] for i in range(N)]
for _ in range(N):
    u, k, *v = map(int, input().split())
    for i in v:
        adjacency_list[u-1][i-1] = 1

WHITE = 0
GLAY = 1
BLACK = 2
colors = [WHITE for _ in range(N)]
d = [0 for _ in range(N)]
f = [0 for _ in range(N)]

dfs()

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

Submission status: Accepted

Solution code:
def depth_search(u, t):
    t += 1
    s.append(u)
    d[u] = t
    for v in range(N):
        if adjacency_list[u][v] == 0:
            continue 
        if d[v] == 0 and v not in s:
            t = depth_search(v, t)
    t += 1
    s.pop()
    f[u] = t
    return t

N = int(input())
adjacency_list = [[0 for j in range(N)] for i in range(N)]
for _ in range(N):
    u, k, *v = input().split()
    for i in v:
        adjacency_list[int(u)-1][int(i)-1] = 1

s = []
d = [0 for _ in range(N)]
f = [0 for _ in range(N)]

t = 0
for u in range(N):
    if d[u] == 0:
        t = depth_search(u, t)

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

Submission status: Accepted

Solution code:
#coding: utf-8

n = int(input())
color = ["white" for i in range(n)]
d = [[] for i in range(n)]
global t
t = 0
M = [[False for i in range(n)] for j in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    u = data[0]
    k = data[1]
    if i == 0:
        start = u
    for v in data[2:2+k]:
        M[u-1][v-1] = True


def search(u,t):
    t += 1
    color[u-1] = "gray"
    d[u-1].append(t)
    for v in range(1,n+1):
        if M[u-1][v-1] and color[v-1] == "white":
            t = search(v,t)
    color[u-1] = "black"
    t += 1
    d[u-1].append(t)
    return t

t = search(start, t)
for i in range(1,n+1):
    if color[i-1] == "white":
        t = search(i, t)

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

Submission status: Accepted

Solution code:

#graphの頂点vertex(インデックス、0オリジン)を深さ優先探索。dis_time:最初に訪れた時のtimeを管理するリスト
#fin_time:その頂点に対して、探索が終わった時のtimeを管理するリスト　tmp_time:現在のtime(関数内で変更できるようにリスト)
def DPS(graph,vertex,dis_time,fin_time,tmp_time):
    tmp_time[0]+=1
    dis_time[vertex]=tmp_time[0]
    for i in range(len(graph[0])):
        if(graph[vertex][i] !=0 and dis_time[i]==0):#枝先の頂点が探索済みでなかったら、
            DPS(graph,i,dis_time,fin_time,tmp_time)
    
    tmp_time[0]+=1
    fin_time[vertex]=tmp_time[0]



#グラフの作成
n=int(input())
graph=[[0]*n for loop in range(n)]
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(tmp_ope[1]):
        graph[tmp_ope[0]-1][tmp_ope[j+2]-1]=1


dis_time=[0]*n
fin_time=[0]*n
tmp_time=[0]
for i in range(n):
    if(dis_time[i]==0):
        DPS(graph,i,dis_time,fin_time,tmp_time)

for i in range(n):
    print(f"{i+1} {dis_time[i]} {fin_time[i]}")

Submission status: Accepted

Solution code:
n = int(input())

adj = [0]*n # adjacent list

for i in range(n):
    tmp = list(map( int, input().split() ) )
    adj[tmp[0]-1] = list(map(lambda x : x - 1, tmp[2:]))

c = ['w']*n # color of each vertex
d = [0]*n # discovery time for each vertex
f = [0]*n  # finish time for each vertex
time = 0

def DFS_visit(u):
    global time
    time += 1
    d[u] = time
    c[u] = 'g'
    for v in adj[u]:
        if c[v] == 'w':
            DFS_visit(v)
    c[u] = 'b'
    time += 1
    f[u] = time
    
for u in range(n):
    if c[u] == 'w':
        DFS_visit(u)
        
        
for u in range(n):
    print(f"{u+1} {d[u]} {f[u]}")

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    in_list = list(map(int, input().split()))
    u = in_list[0]
    graph[u - 1] = in_list[2:]

d = [0 for _ in range(n)]
f = [0 for _ in range(n)]
time = 0

def dfs(now, prev, graph, d, f):
    if d[now] != 0:
        return d, f
    global time
    time += 1
    d[now] = time
    if not graph[now]:
        f[now] = time + 1
        time += 1
        return
    for k in graph[now]:
        if k - 1 == prev or d[k-1] !=0:
            continue
        dfs(k - 1, now, graph, d, f)
    else:
        time += 1
        f[now] = time
    return d, f



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

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    in_list = list(map(int, input().split()))
    u = in_list[0]
    graph[u - 1] = in_list[2:]

d = [0 for _ in range(n)]
f = [0 for _ in range(n)]
time = 0

def dfs(now, prev, graph, d, f, time):
    if d[now] != 0:
        return d, f, time
    time += 1
    d[now] = time
    if not graph[now]:
        f[now] = time + 1
        time += 1
        return d, f, time
    for k in graph[now]:
        if k - 1 == prev or d[k-1] !=0:
            continue
        _, _, time = dfs(k - 1, now, graph, d, f, time)
    else:
        time += 1
        f[now] = time
    return d, f, time



for i in range(n):
    d, f, time = dfs(i, 0, graph, d, f, time)
    print(i+1, d[i], f[i])

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    l=l[2:]
    for v in l:
        nodes[u-1].append(v-1)
    nodes[u-1].sort()

ans=[[0]*2 for i in range(N)]
visited=[False]*N
time=0
def rec(u):
    if visited[u]:
        return
    visited[u]=True
    global time
    time+=1
    ans[u][0]=time
    for v in nodes[u]:
        rec(v)
    time+=1
    ans[u][1]=time

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

Submission status: Accepted

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

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1
        # A[int(j)-1][int(u)-1] = 1

# for row in A:
#     msg = ' '.join(map(str, row))
#     # print(msg)

d = [-1] * n
f = [-1] * n

t = 0

# recursive


def dfs(u):
    global t
    # print('visit:', str(u), str(t))
    t += 1
    d[u] = t
    for i in range(len(A[u])):
        if A[u][i] == 1 and d[i] == -1:
            dfs(i)
    t += 1
    f[u] = t
            


for i in range(n):
    if d[i] == -1:
        # print('start from:', str(i))
        dfs(i)


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

Submission status: Accepted

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

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1
        # A[int(j)-1][int(u)-1] = 1

for row in A:
    msg = ' '.join(map(str, row))
    # print(msg)

d = [-1] * n
f = [-1] * n

t = 0

# # recursive
# def dfs(u):
#     global t
#     # print('visit:', str(u), str(t))
#     t += 1
#     d[u] = t
#     for i in range(len(A[u])):
#         if A[u][i] == 1 and d[i] == -1:
#             dfs(i)
#     t += 1
#     f[u] = t
            

def get_next(u):
    for i in range(len(A[u])):
        if A[u][i] == 1 and d[i] == -1:
            return i
    return None

def dfs(u):
    global t
    s = []
    s.append(u)
    d[u] = t
    while len(s) > 0:
        p = s[-1]
        v = get_next(p)
        # print(p, 'next:', v)
        # t += 1
        # d[p] = t
        # print('poped:', p)
        
        if v is not None:
            
            if d[v] == -1:
                t += 1
                d[v] = t
                s.append(v)
                # print('[append:', v, 'at', t)
        else:
            t += 1
            # print('complete:', p, 'at', t)
            s.pop()
            f[p] = t


# def dfs(u):
#     s = []
#     t = 0
#     s.append(u)
    
#     while len(s) > 0:
#         p = s.pop()
#         print('init', str(p), d[p], t)
#         if d[p] > -1:
#             print('完了')
#             t += 1
#             f[p] = t
#         else:
#             t += 1
#             d[p] = t
#             print('---visit:', str(p), str(t), 'at', t)
#             has_node = False
#             for i in range(len(A[p])):
#                 if A[p][i] == 1 and d[i] == -1:
#                     print('reserve:', str(i))
#                     has_node = True
#                     s.append(i)
#                     break
#             if not has_node:
#                 t += 1
#                 f[p] = t
#         # print('H_complete:', str(p), str(t))
            


t = 0
for i in range(n):
    if d[i] == -1:
        t += 1
        # print('start from:', str(i))
        dfs(i)


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

Submission status: Accepted

Solution code:
# input
n = int(input())
A = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    u, k, *v_list = list(map(int, input().split()))
    for v in v_list:
        A[u-1][v-1] = 1

# init
d = [0] * n
f = [0] * n
t = 0

# recursive
def dfs(u):
    global t
    t += 1
    d[u] = t
    for v in range(n):
        if A[u][v] == 1 and d[v] == 0:
            dfs(v)
    t += 1
    f[u] = t

# dfs
for i in range(n):
    if d[i] == 0:
        dfs(i)

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

Submission status: Accepted

Solution code:
n = int(input())
G = [[] for _ in range(n)]
u1 = 0
for _ in range(n):
    u, k, *v = [int(i) for i in input().split()]
    G[u - 1] = v
    if k != 0 and u1 == 0:
        u1 = u

time = 1
u = u1
D = []
out = [[i+1, 0, 0] for i in range(n)]
T = []
while True:
    if u not in D:
        out[u - 1][1] = time
        D.append(u)
        T.append(u)

    for d in D:
        if d in G[u - 1]:
            idx = G[u - 1].index(d)
            del G[u - 1][idx]

    if G[u - 1] == []:
        time += 1
        out[T.pop() - 1][2] = time
        if T == []:
            if len(D) == n:
                break
            else:
                for ni in range(n):
                    if ni + 1 not in D:
                        u = ni + 1
                        break
                time += 1
                continue
        else:
            u = T[-1]
    else:
        u = G[u - 1].pop(0)
        time += 1

for ni in range(n):
    print(*out[ni])