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:
# coding: UTF-8
from collections import deque
#入力値の整理
n = int(input())
adj={}
visited={}
d={}
f={}
t=0
visited=set()
for i in range(n):
  raw=list(map(int,input().split()))
  u = raw.pop(0)
  k = raw.pop(0)
  raw.sort()
  q = deque(raw)
  adj[u] = q  
  d[u] = -1
  f[u] = -1

next = 1
v = next
d[next] = t + 1
stack = deque()
visited.add(v)

while True:
  t = t+1
  clear = True
  while adj[v]:
    cand = adj[v].popleft()
    if cand not in visited:
      next = cand
      d[next] = t + 1
      visited.add(next)
      clear = False
      break
  if clear:
    f[v] = t + 1
    if stack:
      next = stack.pop()
      v = next
    else:
      end = True
      for i in range(n):
        if i+1 not in visited:
          next = i+1
          end = False
          break
      if end:
        break
      else:
        t = t+1
        v = next
        d[next] = t + 1
        visited.add(v)
  else:
    stack.append(v)
    v = next

#print
i = 0
for j in range(n):
  i += 1
  print(str(i) + " " + str(d[i]) + " " + str(f[i]))

#return d,f

Submission status: Accepted

Solution code:
# coding: UTF-8
from collections import deque
n = int(input())
arrow = {}
visited = set()
d = {}
f = {}


for i in range(n):
  raw = list(map(int,input().split()))
  #print(raw)
  u = raw.pop(0)
  k = raw.pop(0)
  raw.sort()
  q = deque(raw)
  arrow[u] = q
  d[u] = -1
  f[u] = -1

def dfslocal(v,t,arrow,f,d):
  t += 1
  d[v] = t
  visited.add(v)
  #print("First visit to " + str(v) + " at " + str(t) + "!")
  while arrow[v]:
    k = arrow[v].popleft()
    if k not in visited:
      
      t = dfslocal(k,t,arrow,f,d)
  f[v] = t+1
  return t+1

def dfsglobal(arrow,f,d):
  t = 0
  for u in range(n):
    if u+1 not in visited:
      t = dfslocal(u+1,t,arrow,f,d)
  return t

t = dfsglobal(arrow,f,d)

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

Submission status: Accepted

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


if __name__ == '__main__':

    n = int(input())
    M = [[0 for i in range(n)] for j in range(n)]
    for _ in range(n):
        l = list(map(int, input().split(" ")))
        u = l[0]
        k = l[1]
        if k != 0:
            for v in l[2:]:
                M[u-1][v-1] = 1
    
    color = [0]*n
    d = [0]*n
    f = [0]*n
    time = 0
    
    def dfs(u): #depth-first search
        global time
        color[u] = 1
        time += 1
        d[u] = time
        for v in range(n):
            if M[u][v] == 1 and color[v] == 0:
                dfs(v)
        color[u] = 2
        time += 1
        f[u] = time
    
    for u in range(n):
        if color[u] == 0:
            dfs(u)

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

Submission status: Accepted

Solution code:
from sys import stdin

global time
time = 0

def dfs(graph,start,state,discover,finish):

    state[start-1] = 1
    global time
    time = time + 1
    discover[start-1] = time
    # print str(time) + " go to " + str(start)

    neighbours = sorted(graph[start])

    for neighbour in neighbours:
        if state[neighbour-1] == 0:
            dfs(graph,neighbour,state,discover,finish)

    state[start-1] = 2
    time = time + 1
    finish[start - 1] = time
    # print str(time) + " out of " + str(start)

def main():
    # g = {1: [2, 3],
    #      2: [3, 4],
    #      3: [5],
    #                     4: [6],
    #                     5: [6],
    #                     6: []}



    # deal with input
    n = int(stdin.readline())

    g = {}

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

    all_vertex = []

    for i in xrange(n):
        entry = [int(s) for s in stdin.readline().split()[2:]]
        g[i+1] = entry
        all_vertex.append(i+1)



    # exp = []
    # state represent vertex visited state: 0 not visited 1 visiting 2 finished
    state = [0]*n

    for node in all_vertex:
        if state[node-1] == 0:
            dfs(g,node,state,d,f)

    # print  'state ' + str(state)

    # print 'd' + str(d)
    # print 'f' + str(f)

    # deal with output
    for i in xrange(n):
        print str(i+1) + ' ' + str(d[i]) + ' ' + str(f[i])

main()

Submission status: Accepted

Solution code:
def MAIN():
    n = int(input())
    ans = [[i, 0, 0] for i in range((n + 1))]
    G = [[] for _ in range((n + 1))]
    for _ in range(n):
        u, k, *v = map(int, input().split())
        G[u] = v
    cnt = 1
    def dfs(u):
        nonlocal ans
        if ans[u][1] != 0:
            return
        nonlocal cnt
        ans[u][1] = cnt
        cnt += 1
        for v in G[u]:
            dfs(v)
        ans[u][2] = cnt
        cnt += 1
    for i in range(1, n + 1):
        if ans[i][1] == 0:
            dfs(i)
    for i in range(1, n + 1):
        print(" ".join(map(str, ans[i])))
MAIN()

Submission status: Accepted

Solution code:
def MAIN():
    n = int(input())
    ans = [[i, 0, 0] for i in range((n + 1))]
    G = [[] for _ in range((n + 1))]
    for _ in range(n):
        u, k, *v = map(int, input().split())
        G[u] = v
    cnt = 1
    def dfs(u):
        nonlocal ans
        if ans[u][1] != 0:
            return
        nonlocal cnt
        ans[u][1] = cnt
        cnt += 1
        for v in G[u]:
            dfs(v)
        ans[u][2] = cnt
        cnt += 1
    for i in range(1, n + 1):
        if ans[i][1] == 0:
            dfs(i)
    for i in range(1, n + 1):
        print(*ans[i])
MAIN()

Submission status: Accepted

Solution code:
def MAIN():
    n = int(input())
    ans = [[i, 0, 0] for i in range((n + 1))]
    G = [[] for _ in range((n + 1))]
    for _ in range(n):
        u, k, *v = map(int, input().split())
        G[u] = v
    cnt = 1
    def dfs(u):
        nonlocal ans
        if ans[u][1] != 0:
            return
        nonlocal cnt
        ans[u][1] = cnt
        cnt += 1
        for v in G[u]:
            dfs(v)
        ans[u][2] = cnt
        cnt += 1
    for i in range(1, n + 1):
        if ans[i][1] == 0:
            dfs(i)
        print(*ans[i])
MAIN()

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=1;t+=1;D[u]=t
 for v in range(N):
  if M[u][v]and C[v]==0:d(v)
 C[u]=2;t+=1;F[u]=t
N=int(input())
M=[[0]*N for _ in[0]*N]
for e in[list(map(int,input().split()))for _ in[0]*N]:
 for v in e[2:]:M[e[0]-1][v-1]=1
C,D,F=[0]*N,[0]*N,[0]*N
t=0
for i in range(N):
 if C[i]==0:d(i)
for i in range(N):print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=1;t+=1;D[u]=t
 for v in range(N):
  if M[u][v]and C[v]==0:d(v)
 C[u]=2;t+=1;F[u]=t
N=int(input())
M=[[0]*N for _ in[0]*N]
for e in[input().split()for _ in[0]*N]:
 for v in e[2:]:M[int(e[0])-1][int(v)-1]=1
C,D,F=[0]*N,[0]*N,[0]*N
t=0
for i in range(N):
 if C[i]==0:d(i)
for i in range(N):print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=0;t+=1;D[u]=t
 for v in R:
  if M[u][v]and C[v]:d(v)
 t+=1;F[u]=t
N=int(input());R=range(N)
M=[[0]*N for _ in R]
for e in[input().split()for _ in R]:
 for v in e[2:]:M[int(e[0])-1][int(v)-1]=1
C,D,F=[1]*N,[0]*N,[0]*N
t=0
for i in R:
 if C[i]:d(i)
for i in R:print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=0;D[u]=t;t+=1
 for v in M[u]:
  v=int(v)-1
  if C[v]:d(v)
 F[u]=t;t+=1
N=int(input());R=range(N)
M=[input().split()[2:]for _ in R]
C,D,F=[1]*N,[0]*N,[0]*N
t=1
for i in R:
 if C[i]:d(i)
for i in R:print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=0;D[u]=t;t+=1
 for v in M[u]:v=int(v)-1;C[v]and d(v)
 F[u]=t;t+=1
N=int(input());R=range(N)
M=[input().split()[2:]for _ in R]
C,D,F=[1]*N,[0]*N,[0]*N
t=1
for i in R:C[i]and d(i)
for i in R:print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
def d(u):
 global t
 C[u]=1;D[u]=t;t+=1
 for v in M[u]:v=int(v)-1;C[v]or d(v)
 F[u]=t;t+=1
N=int(input());R=range(N)
M=[input().split()[2:]for _ in R]
C,D,F=[0]*N,[0]*N,[0]*N
t=1
for i in R:C[i]or d(i)
for i in R:print(i+1,D[i],F[i])

Submission status: Accepted

Solution code:
class Vertex:
    _id = -1
    _children = []
    _visited = False
    _visited_time = 0
    _all_visited_time = 0

    def __init__(self, i, c):
        self._id = i
        self._children = c

    def getId(self):
        return self._id

    def getChildren(self):
        return self._children

    def isVisited(self):
        return self._visited

    def getVisitedTime(self):
        return self._visited_time

    def setVisitedTime(self, t):
        self._visited_time = t
        self._visited = True

    def getAllVisitedTime(self):
        return self._all_visited_time

    def setAllVisitedTime(self, t):
        self._all_visited_time = t

    def print(self):
        print("{} {} {}".format(self._id, self._visited_time, self._all_visited_time))


n = int(input())
graph = [0 for i in range(n)]
time = 0

# 頂点登録
for i in range(n):
    u = list(map(int, input().split(' ')))
    adj = []
    if u[1] > 0:
        adj = u[2:u[1]+2]
    graph[u[0]-1] = Vertex(u[0], adj)

# DFS
def dfs(v):
    global time
    time += 1
    v.setVisitedTime(time)
    for child in v.getChildren():
        if not graph[child-1].isVisited():
            dfs(graph[child-1])
    time += 1
    v.setAllVisitedTime(time)

# DFS実行
for v in graph:
    if not v.isVisited():
        dfs(v)

# 回答を出力
for v in graph:
    v.print()

Submission status: Accepted

Solution code:
from enum import Enum, auto

class Color(Enum):
    WHITE = auto() # 未訪問の頂点
    GRAY = auto() # 訪問済みだが, 全ての接点の調査は済んでいない状態の接点
    BLACK = auto() # 訪問, 調査済みの接点

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

colors = [] # 頂点の訪問状態
A = [[0 for j in range(n)] for i in range(n)] # 隣接行列
# stack = [] ## スタックによる実装では頂点の保持が必要 => 再帰によって実装

# 隣接行列の初期化
for i in range(n):
    arr = list(map(int, input().split(' ')))
    u, k, v = arr[0], arr[1], arr[2:]
    for j in range(k):
        A[u-1][v[j]-1] = 1

time = 0
def dfs_init():
    global colors
    colors = [Color.WHITE for i in range(n)]
    dfs(0)

def dfs(u):
    global time
    colors[u] = Color.GRAY
    time += 1
    d[u] = time
    for v in range(n):
        if A[u][v] == 1 and colors[v] == Color.WHITE:
            dfs(v)
    colors[u] = Color.BLACK
    time += 1
    f[u] = time

dfs_init()
for u in range(n):
    if colors[u] == Color.WHITE:
        dfs(u)

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

Submission status: Accepted

Solution code:
import abc


class AdjacentGraph:
    """Implementation adjacency-list Graph.
    Beware ids are between 1 and size.
    """
    def __init__(self, size):
        self.size = size
        self._nodes = [[0] * (size+1) for _ in range(size+1)]

    def set_adj_node(self, id_, adj_id):
        self._nodes[id_][adj_id] = 1

    def __iter__(self):
        self._id = 0
        return self

    def __next__(self):
        if self._id < self.size:
            self._id += 1
            return (self._id, self._nodes[self._id][1:])

        raise StopIteration()

    def dfs(self, handler=None):

        visited = []
        while len(visited) < self.size:
            for id_ in range(1, self.size+1):
                if id_ not in visited:
                    stack = [(id_, 0)]
                    break
            while len(stack) > 0:
                i, j = stack.pop()
                if j == 0:
                    if handler:
                        handler.visit(i)
                    visited.append(i)
                    yield i
                try:
                    j = self._nodes[i].index(1, j+1)
                    stack.append((i, j))
                    if j not in visited:
                        stack.append((j, 0))
                except ValueError:
                    if handler:
                        handler.leave(i)


class EventHandler(abc.ABC):
    @abc.abstractmethod
    def visit(self, i):
        pass

    @abc.abstractmethod
    def leave(self, i):
        pass


class Logger(EventHandler):
    def __init__(self, n):
        self.log = [(0, 0)] * n
        self.step = 0

    def visit(self, i):
        self.step += 1
        self.log[i-1] = (self.step, 0)

    def leave(self, i):
        self.step += 1
        (n, m) = self.log[i-1]
        self.log[i-1] = (n, self.step)

    def by_node(self):
        i = 1
        for discover, finish in self.log:
            yield (i, discover, finish)
            i += 1


def run():
    n = int(input())
    g = AdjacentGraph(n)
    log = Logger(n)

    for i in range(n):
        id_, c, *links = [int(x) for x in input().split()]
        for n in links:
            g.set_adj_node(id_, n)

    for i in g.dfs(log):
        pass

    for node in log.by_node():
        print(" ".join([str(i) for i in node]))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import sys
n = int(input())
input_line = [[int(i) for i in str.split()] for str in sys.stdin.read().splitlines()]
for i in range(n):
    input_line[i] = [] if len(input_line[i]) == 2 else input_line[i][2:]
detect_time = [0] * n
finish_time = [0] * n
is_visit = [False] * n
stack = []
time = 0

while(time < n*2):
    time += 1
    id = is_visit.index(False) + 1
    stack.append(id)
    is_visit[id-1] = True
    detect_time[id-1] = time
    while(len(stack) != 0):
        id = stack[-1]
        if len(input_line[id-1]) == 0:
            time += 1
            finish_time[stack.pop()-1] = time
        else:
            detect_id = input_line[id-1].pop(0)
            if is_visit[detect_id-1]:
                continue
            stack.append(detect_id)
            time += 1
            detect_time[detect_id-1] = time
            is_visit[detect_id-1] = True


for id in range(n):
    print('{0} {1} {2}'.format(id+1, detect_time[id], finish_time[id]))

Submission status: Accepted

Solution code:

d = None
f = None


def dfs(g, cur, time):
    global d, f
    d[cur] = time
    for next in g[cur]:
        if d[next] == 0:
            time = dfs(g, next, time+1)
    f[cur] = time + 1
    return time + 1


def main():
    global d, f
    n = int(input())
    g = [[] for _ in range(n)]
    d = [0 for _ in range(n)]
    f = [0 for _ in range(n)]
    for _ in range(n):
        inp = list(map(int, input().split()))
        m = inp[0] - 1
        k = inp[1]
        for i in range(k):
            g[m].append(inp[i+2] - 1)
    time = 1
    for i in range(n):
        if d[i] == 0:
            time = dfs(g, i, time) + 1
    for i in range(n):
        print(i+1, d[i], f[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
m = [[0 for j in range(n)] for i in range(n)]
color = [0 for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
time = [0]


def dfs(u):
    color[u] = 1
    time[0] += 1
    d[u] = time[0]
    for i in range(n):
        if m[u][i] == 1 and color[i] == 0:
            dfs(i)

    color[u] = 2
    time[0] += 1
    f[u] = time[0]


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(2, len(data)):
            m[data[0]-1][data[j]-1] = 1

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
g = []
for i in range(n):
    a = list(map(int,input().split()))
    g.append(a[2:])
d = [0]*n
f = [0]*n
global t
t = 1
d[0] = 1
x = 1
def find(x):
    global t
    if len(g[x-1]) == 0:
        t += 1
        f[x-1] = t
    else:
        for i in g[x-1]:
            if d[i-1] == 0:
                t += 1
                d[i-1] = t
                find(i)
        t += 1
        f[x-1] = t

find(x)
for i in range(n):
    if d[i] == 0:
        t += 1
        d[i] = t
        find(i+1)
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):
    a = list(map(int,input().split()))
    g.append(a[2:])
d = [0]*n
f = [0]*n
global t
t = 0

def find(x):
    global t
    if len(g[x-1]) == 0:
        t += 1
        f[x-1] = t
    else:
        for i in g[x-1]:
            if d[i-1] == 0:
                t += 1
                d[i-1] = t
                find(i)
        t += 1
        f[x-1] = t

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

Submission status: Accepted

Solution code:
global t
t = 0

class Node:
    def __init__(self, num, deg, neib):
        self.num = num
        self.deg = deg
        self.neib = neib

def dfs(G, d, f, now): #now:1,2,...
    #print("now:",now)
    global t
    t += 1
    #print("t:",t)
    if d[now-1] != 0:
        t -= 1
        #print("has searched or hit roop")
    else:
        d[now-1] = t
        #print("d:",d)
        #print("f:",f)
        for i in G[now-1].neib:
            #print("i:",i)
            if i != -1:
                #print("next node")
                dfs(G, d, f, i)
            #else: print("end of branch")
        t += 1
        f[now-1] = t

        #print("f:",f)


dnum = int(input()) #頂点数
N = []
for i in range(dnum):
    data = input().split()
    
    u = int(data[0])
    k = int(data[1])
    if k > 0:
        v = list(map(int, data[2:]))
    else:
        v = [-1]

    node = Node(u,k,v)
    N.append(node)

d = [0]*dnum #find time
f = [0]*dnum #finish time

while 0 in d:
    s = d.index(0)
    dfs(N, d, f, s+1)
    #print("looks like finish")

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

Submission status: Accepted

Solution code:
n = int(input())
B = [[0 for i in range(n)] for j in range(n)]
chk = [0 for i in range(n)]
s = []
i_array = [0 for i in range(n)]
time = 1
node_start_time = [0 for i in range(n)]
node_finish_time = [0 for i in range(n)]

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

for i in range(n):
    if(chk[i] == 1):
        continue
    chk[i] = 1
    node_start_time[i] = time
    time += 1
    s.append(i)
    while(len(s) != 0):
        flag = 0
        v = s[len(s)-1]
        for j in range(i_array[v],n):
            if(B[v][j] == 1 and chk[j] == 0):
                chk[j] = 1
                s.append(j)
                node_start_time[j] = time
                time += 1
                i_array[v] = j+1
                flag = 1
                break
        if(flag == 0):
            s.pop()
            node_finish_time[v] = time
            time += 1

for i in range(n):
    print(i+1,node_start_time[i],node_finish_time[i])

Submission status: Accepted

Solution code:
#16D8101014F KurumeRyunosuke 2018/6/20

n=int(input())
ls=[[0 for i in range(n)]for j in range(n)]
for i in range(n):
	tmp=input().split()
	for j in range(int(tmp[1])):
		ls[i][int(tmp[j+2])-1]=1

"""
for i in range(n):
    for j in range(n):
        if(j!=n-1):
            print(int(ls[i][j]), end=' ')
        else:
            print(int(ls[i][j]))
"""
stuck=[0]
count=1
d=[0 for i in range(n)]
f=[0 for i in range(n)]
d[0]=count
for i in range(n):
	ls[i][0]=0

while True:
	count+=1
	p=0
	#print("S",d)
	for i in range(n):
		if ls[stuck[len(stuck)-1]][i] is not 0:
			ls[stuck[len(stuck)-1]][i]=0
			p=1
			#print(stuck)
			stuck.append(i)
			d[stuck[len(stuck)-1]]=count
			break
	#print(d,"**")
	if p is 1:
		for i in range(n):
			ls[i][stuck[len(stuck)-1]]=0

	if p is 0:
		#print("//",count)
		a=stuck.pop()
		f[a]=count
		for i in range(n):
			ls[a][i]=0
	#print(d,"¥¥¥")
	if len(stuck) is 0:
		t=0
		for i in range(n):
			for j in range(n):
				if ls[i][j] is not 0 and t is 0:
					count+=1
					stuck.append(i)
					d[stuck[len(stuck)-1]]=count
					#print(i,"***")
					t=1
					
		if t is 0:
			break
		#print("break")
	#print("G",d,f,count)

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

Submission status: Accepted

Solution code:
def dfs(adj, s, d, f, now):
    now += 1
    d[s] = now
    for t in adj[s]:
        if t != s and f[t] < 0 and d[t] < 0:
            d, f, now = dfs(adj, t, d, f, now)
    now += 1
    f[s] = now
    return d, f, now


n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n):
    s = [int(x) for x in input().split()]
    u = s[0]
    for v in s[2:]:
        adj[u - 1].append(v - 1)
    adj[u - 1].sort()

d = [-1 for _ in range(n)]
f = [-1 for _ in range(n)]
now = 0
for s in range(n):
    if f[s] < 0:
        d, f, now = dfs(adj, s, d, f, now)

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

Submission status: Accepted

Solution code:
n=int(input())

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

stk=[]
stk.append(0)
time=1
d=[0 for i in range(n)]
f=[0 for i in range(n)]
know=[0 for i in range(n)]

def dfs(x):
	global time
	know[x]=1
	d[x]=time
	time+=1
	for n in next[x]:
		if know[n]==0:
			dfs(n)
	f[x]=time
	time+=1
	
for i in range(n):
	if know[i]==0:
		dfs(i)

for i in range(n):
	out=[]
	out.append(i+1)
	out.append(d[i])
	out.append(f[i])
	print(*out)

Submission status: Accepted

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 


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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 i+1 not in stack 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: Accepted

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 and i+1 not in stack:
                stack.append(i+1)
                t+=1
                d[i]=t
                break
            elif i==n-1:
                t+=1
                f[stack[-1]-1]=t
                v.append(stack.pop())
            else: pass
            #print("i=",i)
            #print("stack ",stack)
            #print("v ",v)
    t+=1
#print("d=",d," f=",f)
for i in range(n):
    print(i+1,d[i],f[i])

Submission status: Accepted

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)
		time+=1

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

Submission status: Accepted

Solution code:
cnt = 1
def dep(G,s_cnt,f_cnt,np):
    global cnt
    s_cnt[np] = cnt
    cnt += 1
    for i in range(n):
        if G[np][i] == 1 and s_cnt[i] == 0:
            dep(G,s_cnt,f_cnt,i)
    f_cnt[np] = cnt
    cnt += 1
    

n = int(input())
G = [[0 for i in range(n)] for j in range(n)]
s_cnt = [0 for i in range(n)]
f_cnt = [0 for i in range(n)]

for i in range(n):
    S = list(map(int, input().split()))
    tmp_n = S[1]
    for j in range(tmp_n):
        G[i][S[j+2]-1] = 1
        
for i in range(n):
    if s_cnt[i]==0:
        dep(G,s_cnt,f_cnt,i)

for i in range(n):
    print(i+1,s_cnt[i],f_cnt[i])

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:
#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:
            if 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:
                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: Accepted

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

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


time = 1
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
    
        if v != None:
            objList[index] = v
            if c[v.key - 1] == "white":
                index = v.key - 1
                v = objList[index]
                c[v.key-1] = "gray"
                time += 1
                d[index] = time
                S.append(v.key)

           
                
        else:
            S.pop()
            c[u.key-1] = "black"
            time += 1
            f[index] = time
    return time


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

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