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:
# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4647653#1



import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self,i,adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def path_detector(self, start=0, time=0):
        """
        :param p: スタート地点
        :return: 各点までの距離と何番目に発見したかを返す
        """

        edge2= []
        for i in range(self.n):
            edge2.append(sorted(self.edge[i], reverse=True))

        p, t = start, time
        self.parent[p] = -2
        full_path = [(p + self.decrement,t)]
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                self.parent[q] = p
                p, t = q, t + 1
                full_path.append((p + self.decrement, t))
            else:
                """ 探索完了時の処理 """
                full_path.append((p + self.decrement, t))
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                """"""""""""""""""""
        return full_path

    def path_list(self):
        """
        :return: 探索経路を返す。
        """
        self.parent = [-1]*self.n
        res = []
        for p in range(self.n):
            if self.parent[p] == -1:
                res.append(self.path_detector(start=p, time=1))
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edge[x]:
                G.add_edge(x + self.decrement, y + self.decrement)
        nx.draw_networkx(G)
        plt.show()

def make_graph(dictated=False, decrement=True):
    """
    自己ループの無いグラフを生成。N>=2
    :param dictated: True = 有効グラフ
    :param decrement: True = 1-indexed
    :return:
    """
    import random
    N = random.randint(2, 5)
    if N > 2:
        M_max = (3*N-6)*(1+dictated)
    else:
        M_max = 1
    graph = Graph(N, dictated, decrement)
    for _ in range(random.randint(0,M_max)):
        graph.add_edge(*random.sample(range(decrement, N+decrement), 2))
    return graph

##################################################################
# 入力が隣接リストの場合
##################################################################

N = int(input())  # 頂点数

graph = Graph(N,dictated=True, decrement=True)

for i in range(N):  # [[頂点1と連結している頂点の集合], [頂点2と連結している頂点の集合],...]
    points = list(map(int, input().split()))[2:]
    graph.add_adjacent_list(i, points)


data = graph.path_list()

from itertools import chain
data = list(chain.from_iterable(data))

res = [[i+1,0,0] for i in range(N)]
for time, a in enumerate(data, start=1):
    i = a[0] - 1
    if res[i][1]:
        res[i][2] = time
    else:
        res[i][1] = time

for a in res:
    print(*a)

Submission status: Accepted

Solution code:
n = int(input()) # 点の総数
path = list() # path[p] : 点pから行ける点のリスト
path.append([])
for _ in range(n):
    tmp = list(map(int, input().split())) # tmp[0]から行ける点はtmp[1]個あり、それはtmp[2:]
    path.append(tmp[2:])

d = [0]*(n+1) # 最初に発見した時刻
f = [0]*(n+1) # 隣接リストを調べ終えた時刻

TIME = 0

def dfs(p, d, f):
    global TIME
    TIME += 1
    d[p] = TIME # 来訪時刻の記録

    for nxt in path[p]: #繋がってる点の内
        if d[nxt] == 0: # 未探索の場合には
            dfs(nxt, d, f) # 先に進む
    
    TIME += 1
    f[p] = TIME # 繋がってる全ての点を探索し終えたらその点でやることは終わり

    
    return     
    
for start in range(1, n+1):
    if d[start] == 0:
        dfs(start, d, f)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
idx = 1


def resolve():
    def dfs(v):
        global idx
        begin[v] = idx
        idx += 1
        for u in edge[v]:
            if begin[u] != 0:
                continue
            else:
                dfs(u)
        end[v] = idx
        idx += 1

    n = int(input())
    edge = [[] for _ in range(n)]
    for _ in range(n):
        u, k, *V = map(int, input().split())
        for v in V:
            edge[u - 1].append(v - 1)

    begin = [0] * n
    end = [0] * n
    for i in range(n):
        if begin[i] == 0:
            dfs(i)
    for i in range(n):
        print(i + 1, begin[i], end[i])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict


def dfs(v, t):
    if start[v] == 0:
        start[v] = t
        t += 1
    else:
        return t

    for nv in graph[v]:
        t = dfs(nv, t)

    end[v] = t
    t += 1

    return t


n = int(input())

graph = defaultdict(list)

for _ in range(n):
    u, k, *v = map(int, input().split())
    for v in v:
        graph[u].append(v)

start = [0] * (n + 1)
end = [0] * (n + 1)


t = 1

for i in range(1, n + 1):
    t = dfs(i, t)

for i in range(1, n + 1):
    print(i, start[i], end[i])

Submission status: Accepted

Solution code:
N = int(input())
adj_list = [ [] for _ in range(N+1) ]
for _ in range(N):
  lst = list(map(int,input().split()))
  node = lst[0]
  if lst[1] != 0:
    adj_list[node] = lst[2:]


visited = [False] * (N+1)
arrived = [-1] * (N+1)
left = [-1] * (N+1)

time = 0
def dfs(node):
  global time

  arrived[node] = time
  visited[node] = True

  for nei in adj_list[node]:
    if not visited[nei]:
      time += 1
      dfs(nei)
  else:
    time += 1
    left[node] = time

for i in range(1, N+1):
  if not visited[i]:
    time += 1
    dfs(i)

for i in range(1, N+1):
  print(i, arrived[i], left[i])

Submission status: Accepted

Solution code:
n = int(input())
link = {}

for i in range(n):
    a = list(map(int, input().split()))
    a.reverse()

    u, k = a.pop(), a.pop()
    link[u] = []
    for j in range(k):
        link[u] += [a.pop()]

d, f = {}, {}
t = 0


def dfs(u):
    global t
    t += 1
    d[u] = t

    for v in link[u]:
        if v not in d: dfs(v)

    if u not in f:
        t += 1
        f[u] = t


for u in range(1, n + 1):
    if u not in d: dfs(u)

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    u,k,v=0,0,[[] for _ in range(n+1)]
    for i in range(n):
        l=list(map(int,input().split()))
        u=l[0]
        for j in l[2:]:
            v[u].append(j)
    d=[0]*(n+1)
    f=[0]*(n+1)

    def dfs(s,t):
        d[s]=t
        for i in v[s]:
            if d[i]==0:
                t=dfs(i,t+1)
        f[s]=t+1
        return t+1

    s,t=1,1
    while 0 in d[1:]:
        T=dfs(s,t)
        for i in range(1,n+1):
            if d[i]==0:
                s=i
                t=T+1
                break

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
u = []
k = []
v = []

for i in range(n):
    tmp = list(map(int, input().split()))
    u.append(tmp[0])
    k.append(tmp[1])
    if tmp[1] != 0:
        v.append(tmp[2:])
    else:
        v.append([])
        
check = [0]*n
intime = [0]*n
outtime = [0]*n
time = 1

def dfs(v, start):
    d = deque()
    d.append(start)
    global check
    global intime
    global outtime
    global time
    check[start-1] = 1
    intime[start-1] = time
    time += 1
    while len(d) > 0:
        visit = d[-1]
        tf = True
        for dtn in v[visit-1]:
            if check[dtn-1] == 0:
                d.append(dtn)
                check[dtn-1] = 1
                intime[dtn-1] = time
                time += 1
                tf = False
                break
        if tf:
            outtime[visit-1] = time
            d.pop()
            time += 1

dfs(v, 1)
for i in range(n):
    if check[i] == 0:
        dfs(v, i+1)
for i in range(n):
    print(i+1, intime[i], outtime[i])

Submission status: Accepted

Solution code:
n = int(input())
d = [0]*n
f = [0]*n
G = [[] for _ in range(n)]
for _ in range(n):
    l = list(map(int, input().split()))
    u, k = l[:2]
    l = list(map(lambda x: x-1, l[2:]))
    G[u-1] = l

timestamp = [i+1 for i in range(2*n)]
def dfs(node):
    global d,f,G,timestamp
    if d[node]>0:
        return False
    d[node] = timestamp.pop(0)
    for v in G[node]:
        dfs(v)
    if f[node]==0:
        f[node] = timestamp.pop(0)
    return True
for i in range(n):
    dfs(i)
    
for i in range(n):
    print(i+1, d[i], f[i])

Submission status: Accepted

Solution code:
n=int(input())
g=[]
for i in range(n):
    u,k,*varray= map(int,input().split())
    g.append(varray)

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

def dfs(src):
    global time
    d[src]= time
    time+=1
    for i in g[src]:
        if d[i-1]== -1:
            dfs(i-1)
    f[src]= time
    time+=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:
n=int(input())
D=[0]*(n+1)
F=[0]*(n+1)
v=[[] for i in range(n+1)]
flg=True
t=1
for i in range(n):
  a=list(map(int,input().split()))
  v[a[0]]=sorted(a[2:])

def dfs(p):
  global t
  if D[p]!=0: return
  D[p]=t
  t+=1
  for i in v[p]:
    if D[i]==0: dfs(i)
  F[p]=t
  t+=1

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

for i in range(1,n+1):
  print(f'{i} {D[i]} {F[i]}')

Submission status: Accepted

Solution code:
N = int(input())
M = []
for i in range(N):
    a = list(map(int,input().strip().split()))
    b = [int(i+1 in a[2:]) for i in range(N)]
    M.append(b)

time = 1
D = [-1 for _ in range(N)]
F = [-1 for _ in range(N)]
def dfs(src):
    global time # 関数内でglobal変数の書き換えることを宣言
    D[src] = time # 訪問時刻を記録
    time += 1
    for dst in range(N):
        # srcからdstに移動可能で、dstが未訪問だったら
        if M[src][dst] == 1 and D[dst] == -1:
            dfs(dst)
    F[src] = time # 訪問終了時刻を記録
    time += 1
    # 関数の終わりで親に戻る(青矢印)

for root in range(N):
    # 番号が若い節点から
    if D[root] == -1:
        # D[root]が未訪問だったら
        dfs(root) # dfsを始める

[print(i+1, D[i], F[i]) for i in range(N)]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

G = [[] for _ in range(105)]
begin = [-1] * 105
end = [-1] * 105

t = 1
def dfs(v):
    global t
    begin[v] = t
    t += 1
    for e in G[v]:
        if begin[e] < 0:
            dfs(e)
    end[v] = t
    t += 1

def main():
    N = int(input())
    for i in range(N):
        A = list(map(int,input().split()))
        for a in A[2:]:
            G[i].append(a - 1)
    
    for i in range(N):
        if begin[i] < 0:
            dfs(i)
    for i in range(N):
        print(i + 1,begin[i],end[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

adj = [[] for _ in range(N)]

for i in range(N):
    line = list(map(int, input().split()))
    u = line[0] - 1
    if line[1] == 0:
        continue
    vs = line[2:]
    for v in vs:
        adj[u].append(v - 1)

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

def dfs(v, t):
    d[v] = t
    nx = t + 1
    for u in adj[v]:
        if d[u] > -1:
            continue
        nx = dfs(u, nx)
    f[v] = nx
    return f[v] + 1

nx = 1
for i in range(N):
    if d[i] > - 1:
        continue
    nx = dfs(i, nx)

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

Submission status: Accepted

Solution code:
N = int(input())
UKV = [list(map(int,input().split())) for _ in range(N)]

seen = [False]*N
first_time = [-1]*N
last_time = [-1]*N
time = 0
def dfs(G, v):
    global seen
    global first_time
    global last_time
    global time
    seen[v-1] = True
    time += 1
    first_time[v-1] = time
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)
    time += 1
    last_time[v-1] = time

G = {}
for ukv in UKV:
    G[ukv[0]] = sorted(ukv[2:])
for i in range(1,N+1):
    if seen[i-1]:
        continue
    dfs(G, i)

for i in range(1,N+1):
    print(i,first_time[i-1],last_time[i-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

        while stack:
            s = stack[-1]
            k = ukv[s][1]
            if k == 0:
                stack.pop()
                time += 1
                f[s] = time
            else:
                ukv[s][1] -= 1
                v = ukv[s].pop(2)
                if v not in visited:
                    stack.append(v)
                    visited.append(v)
                    time += 1
                    d[v] = time

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

Submission status: Accepted

Solution code:
n=int(input())
G=[]
for i in range(n):
    L=list(map(int,input().split()))
    G.append(L[2:])
    for j in range(len(G[-1])):
        G[-1][j]-=1

Forder=[-1]*n
Lorder=[-1]*n
ptr=1
def dfs(v):
    #print(v)
    #print(G[v])
    #print()
    global ptr

    Forder[v]=ptr
    ptr+=1

    for next in G[v]:
        if Forder[next]!=-1:
            continue
        dfs(next)
    
    Lorder[v]=ptr
    ptr+=1

#while True:
#    #print(Forder,Lorder)
#    for i in range(n):
#        if Forder[i]!=-1 and Lorder[i]!=-1:
#            pass
#        else:
#            dfs(i)
#            continue
#
#        if i==n-1:
#            break
#    else:
#        continue
#    break
#
#for i in range(n):
#    print(i+1,Forder[i],Lorder[i])

##########
for i in range(n):
    if Forder[i]==-1 or Lorder[i]==-1:
        dfs(i)

for i in range(n):
    print(i+1,Forder[i],Lorder[i])

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(n):
        l=list(map(int,input().split()))
        nList[l[0]]=l[2:]
    return n,nList

WHITE=0
GRAY=1
BLACK=2
color=[]
d=[]
f=[]
_time=0

def dfs(u,nList):
    global color
    global d
    global f
    global _time

    S=[]

    if(color[u]==WHITE):
        S.append(u)
        color[u]=GRAY
        _time+=1
        d[u]=_time

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

def next(u,nList):
    global color
    for t in nList[u]:
        if color[t]==WHITE:
            return t
    else:
        return -1

def main(n,nList):
    global color
    global d
    global f

    color=[WHITE]*(n+1)
    d=[0]*(n+1)
    f=[0]*(n+1)

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

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)

Submission status: Accepted

Solution code:
# 24
# ALDS_11_B - 深さ優先探索

from collections import deque

n = int(input())
u_l = []
k_l = []
v_l = []
for i in range(n):
    _in = input()
    _v_l = []
    for j,_ in enumerate(_in.split()):
        if j == 0:
            u_l.append(int(_))
        elif j == 1:
            k_l.append(int(_))
        else:
            _v_l.append(int(_))
    v_l.append(_v_l)

def dfs(v):
    global count
    c_l[v] = True
    d_l[v] = count
    count += 1
    for i in range(k_l[v]):
        _v = v_l[v][i]-1
        if not c_l[_v]:
            dfs(_v)
    f_l[v] = count
    count += 1

d_l = [None]*n
f_l = [None]*n
c_l = [False]*n
count = 1
while False in c_l:
    dfs(c_l.index(False))

for idx, d, f in zip(list(range(1,n+1)), d_l, f_l):
    print(idx, d, f)

Submission status: Accepted

Solution code:
def solve(v, g, ans, time):
    if ans[v]["found"] != 10**9:
        return time
    time += 1
    # print(v + 1, time, file=sys.stderr)
    ans[v]["found"] = time
    for a in g[v]:
        time = solve(a, g, ans, time)
    time += 1
    # print(v + 1, time, file=sys.stderr)
    ans[v]["complete"] = time
    return time


def resolve():
    n = int(input())
    V = [list(map(int, input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for v, k, *a in V:
        v -= 1
        for ai in a:
            ai -= 1
            g[v].append(ai)
    ans = [{"found": 10**9, "complete": -1} for _ in range(n)]
    time = solve(0, g, ans, 0)
    for i in range(n):
        if ans[i]["found"] == 10**9:
            solve(i, g, ans, time)
        print(i + 1, ans[i]["found"], ans[i]["complete"])


resolve()

Submission status: Accepted

Solution code:
#ALDS_11_B - 深さ優先探索
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)#再帰回数の上限

def DFS(u, cnt):
    visited.add(u)
    first_contact = cnt
    
    cnt += 1
    for nb in edge[u]:
        if nb not in visited:
            cnt = DFS(nb, cnt)
    
    stamp[u] = first_contact, cnt
    return cnt+1
    

N = int(input())
edge = [[] for i in range(N)]
for _ in range(N):
    tmp = list(map(int,input().split()))
    if tmp[1] != 0:
        edge[tmp[0]-1] = list(map(lambda x: int(x-1),tmp[2:]))

stamp = [None]*N
visited = set()

c = 1
for i in range(N):
    if i not in visited:
        c = DFS(i, c)
        
for i,s in enumerate(stamp):
    print(i+1,*s)

Submission status: Accepted

Solution code:
def dfs(adjlist,v):
    global d,f,t
    d[v-1]=t
    t+=1
    for node in adjlist[v-1]:
        if d[node-1]<0 and node>0:
            dfs(adjlist,node)
    f[v-1]=t
    t+=1

n=int(input())
adjlist=[list(map(int,input().split()))[2:] for _ in range(n)]
d=[-1]*n
f=[-1]*n
t=1
for i in range(1,n):
    if d[i-1]<0:
       dfs(adjlist,i)
for i in range(n):
    print("{} {} {}".format(i+1,d[i],f[i]))

Submission status: Accepted

Solution code:
n = int(input())
G = [[] for i in range(n+1)] #G(i): 頂点iと隣接する頂点のlist
for i in range(n):
    a = [int(i) for i in input().split()]
    G[a[0]] = a[2:]
    G[a[0]].sort()

d = [0] * (n+1)
f = [0] * (n+1)

seen = [0] * (n+1) #頂点iが訪問済みの場合 seen[i] = 1
t = 0

def dfs(s):
    global t
    seen[s] = 1
    d[s] = t
    for i in G[s]:
        if seen[i] == 0:
            t += 1
            dfs(i)
    t += 1
    f[s] = t

for i in range(1, n+1):
    if not seen[i]:
        t += 1
        dfs(i)

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 9)

n = int(input())

graph = []

for _ in range(n):
    tmp = list(map(int, input().split()))

    if tmp[1] == 0:
        graph.append([])
        continue
    else:
        graph.append(list(map(lambda x: x - 1, tmp[2: tmp[1] + 2])))

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

time = 1


def dfs(x):
    if d[x] != -1:
        return

    global time

    d[x] = time
    time += 1

    for n in graph[x]:
        dfs(n)

    f[x] = time
    time += 1


for i in range(n):
    dfs(i)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    N = int(sys.stdin.readline())
    L1 = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #print(L1)
    edge = [[] for _ in range(N+1)]
    for row in L1:
        for ele in row[2:]:
            edge[row[0]].append(ele)
            #edge[ele].append(row[0])

    #print(edge)
    sys.setrecursionlimit(1000)
    
    go = [-1 for _ in range(N+1)]
    go[0], go[1] =0, 1
    back = [-1 for _ in range(N+1)]
    
    d = [1]
    def dfs(p):
        if edge[p]:
            for c in edge[p]:
                if go[c]==-1:
                    d[0]+=1
                    go[c] = d[0]
                    dfs(c)
        
        #抜ける順
        d[0]+=1
        back[p] =d[0]
                
    dfs(1)
    for i in range(2, N+1):
        if go[i] ==-1:
            d[0]+=1
            go[i] = d[0]
            dfs(i)
    for i in range(1, N+1):
        print(i, go[i], back[i])




if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
t = 1
v, d, f = {}, {}, {}

def dfs(i):
  global t, v, d, f
  if i in d:
    return
  if i != 0:
    d[i] = t
    t += 1
  for j in v[i]:
    dfs(j)
  if i != 0:
    f[i] = t
    t += 1

n = int(input())
v[0] = list(range(1, n+1))
for i in range(n):
  tmp = list(map(int, input().split()))
  v[tmp[0]] = tmp[2:]
  v[tmp[0]].sort()
dfs(0)
for i in range(n):
  print("{} {} {}".format(i+1, d[i+1], f[i+1]))

Submission status: Accepted

Solution code:
def dfs(v):  # vを訪問する
    global time
    seen[v] = 1
    start[v] = time
    time += 1

    for next_v in graph[v]:
        if seen[next_v]: continue
        dfs(next_v)
    
    end[v] = time
    time += 1


n = int(input())
graph = []
for _ in range(n):
    line = list(map(int, input().split()))
    graph.append([v - 1 for v in line[2:]])

seen = [0] * n  # 0: 未訪問、1: 訪問済
start = [0] * n
end = [0] * n
time = 1

for v in range(n):
    if not seen[v]: dfs(v)

for i in range(n):
    print(i+1, start[i], end[i])

Submission status: Accepted

Solution code:
import sys

n = int(input())
G = [None]*(n+1)
for i in range(n):
    u, k, *vs = map(int, input().split())
    G[u] = vs

d = [-1]*(n+1)
f = [-1]*(n+1)
lb = iter(range(1, 2*n+1)).__next__
def dfs(v):
    d[v] = lb()
    for w in G[v]:
        if d[w] != -1: #already visited
            continue
        dfs(w)
    f[v] = lb()

for v in range(1, n+1):
    if d[v] != -1:
        continue
    dfs(v)

for v in range(1, n+1):
    print(f"{v} {d[v]} {f[v]}")

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
color=["w"]*(N+1)
start=[None]*(N+1)
finish=[0]*(N+1)
rinsetu=[[] for i in range(N+1)]
for i in range(1,N+1):
    a=list(map(int,input().split()))
    a=a[2:]
    rinsetu[i]=a
def dfs(i,t):
    if color[i]=="w":
        t+=1
        start[i]=t
        color[i]="g"
        for j in rinsetu[i]:
            t=dfs(j,t)
        t+=1
        finish[i]=t
        return t
    else:return t
t=dfs(1,0)
while(None in start[1:]):
    a=start[1:].index(None)
    t=dfs(a+1,t)

for i in range(1,N+1):
    print("%d %d %d" %(i,start[i],finish[i]))

Submission status: Accepted

Solution code:
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n):
    u, k, *v = map(int, input().split())
    u -= 1
    G[u].extend(v)
seen = [False] * n
d = [-1] * n
f = [-1] * n
t = 1

def dfs(v):
    global t
#     print(v+1, t)
    d[v] = t
    t += 1
    seen[v] = True
    for next_v in G[v]:
        next_v -= 1
        if not seen[next_v]:
            t = dfs(next_v)
    f[v] = t
    t += 1
    return t

def main():
#     todo = []
#     seen[0] = True
    for i in range(n):
        if not seen[i]:
            dfs(i)
    for i in range(n):
        print(i+1, d[i], f[i])
#     print(G)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)

n = int(input())
X = []
for _ in range(n):
    x = list(map(int, input().split()))
    if x[1] != 0:
        X.append(x[2:])
    else:
        X.append([])

df = [[0, 0] for _ in range(n)]
t = 0
def search(i = 0):
    global t
    if df[i][0] == 0:
        t += 1
        df[i][0] = t
    for x in X[i]:
        if df[x - 1][0] == 0:
            search(x - 1)
    if df[i][1] == 0:
        t += 1
        df[i][1] = t

for i in range(n):
    search(i)

for i, x in enumerate(df):
    print('{} {} {}'.format(i + 1, x[0], x[1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import deque

n = int(input())
u = [[] for i in range(n+1)] #隣接リスト
for i in range(n):
    v = list(map(int, input().split()))
    u[v[0]] = v[1:] #v = [次数, 頂点...]

d = [-1] * (n+1)
f = [-1] * (n+1)
visited = [False] * (n+1)
visited[0] = True
time = 1

#再帰
def dfs(c):
    global time
    d[c] = time
    time += 1
    visited[c] = True
    for i in range(1, u[c][0]+1):
        if not visited[u[c][i]]:
            dfs(u[c][i])
    f[c] = time
    time += 1
"""
探索は元の始点から到達可能なすべての頂点を発見するまで続き、
未発見の頂点が残っていれば、
その中の番号が一番小さい１つを新たな始点として探索を続けます。
"""
while False in visited:
    dfs(visited.index(False))

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

Submission status: Accepted

Solution code:
def dfs(v, time_, d, f, dp):
    if d[v] == 0:
        d[v] = time_
    for i in range(len(dp[v])):
        if d[dp[v][i]] == 0:
            time_ = dfs(dp[v][i], time_ + 1, d, f, dp)
    f[v] = time_ + 1
    return time_ +  1


def main():
    N = int(input())
    dp = [[] for i in range(N)]
    for i in range(N):
        line = [int(k) for k in input().split()]
        for j in range(len(line)):
            if j == 0 or j == 1:
                continue
            dp[line[0] - 1].append(line[j] - 1)

    d = [0] * N
    f = [0] * N
    time_ = 1
    for i in range(N):
        if d[i] == 0:
            time_ = dfs(i, time_, d, f, dp)
            time_ += 1
    for i in range(N):
        print(i + 1, d[i], f[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
time = 1
def dfs(node):
    global time
    if visited[node] != -1:
        return
    visited[node] = 0
    d[node] = time
    time += 1
    for v in edge[node]:
        dfs(v)
    f[node] = time
    time += 1

if __name__ == "__main__":
    n = int(input())
    edge = []
    for i in range(n):
        u,k,*v_li = map(int,input().split())
        for j in range(len(v_li)):
            v_li[j] -= 1
        u-=1
        edge.append(v_li)
    d = {}
    f = {}
    visited = [-1]*n
    
    for i in range(n):
        dfs(i)
    for i in range(n):
        print(i+1,d[i],f[i])

Submission status: Accepted

Solution code:
# ALDS_11_B - 深さ優先探索
import sys

n = int(input())
e = [None] * n
for _ in range(n):
    u, k, *v = map(int, sys.stdin.readline().strip().split())
    e[u - 1] = [i - 1 for i in v]


S = []  # stack
time = 0
t_in = [0] * n
t_out = [0] * n
fp = [False] * n  # foot print  訪問の記録


def dfs(u):
    global time

    S.append(u)
    time += 1
    t_in[u] = time
    fp[u] = True

    while S:
        u = S[-1]

        v = None
        for i in e[u]:
            if fp[i] is False:
                v = i
                break

        time += 1
        if v is not None:
            S.append(v)
            t_in[v] = time
            fp[v] = True

        else:
            v = S.pop()
            t_out[v] = time


while False in fp:
    dfs(fp.index(False))

for i in range(n):
    print(f'{i + 1} {t_in[i]} {t_out[i]}')

Submission status: Accepted

Solution code:
N = int(input())

nodes = [tuple(map(int, input().split(' '))) for _ in range(N)]
d = [-1 for _ in range(N + 1)]
f = [-1 for _ in range(N + 1)]

clock = 0


def dfs(node):
    global clock
    if d[node] == -1:
        clock += 1
        d[node] = clock
    neighbors = sorted(nodes[node - 1][2:])

    for neighbor in neighbors:
        if d[neighbor] == -1:
            dfs(neighbor)

    if f[node] == -1:
        clock += 1
        f[node] = clock


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