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:
def dfs(u):
    global time
    time+=1
    color[u]='gray'
    d[u]+=time
    for v in xrange(n):
        if m[u][v]!=0 and color[v]=="white":
            dfs(v)
    time+=1
    color[u]="black"
    f[u]+=time
    

n=input()
info=[0]*n
color=["white"]*n
m=[[0]*n for _ in xrange(n)]
d=[0]*n
f=[0]*n
for i in xrange(n):
    info[i]=map(int,raw_input().split())
    if info[i][1]==0:
        pass
    else:
        for j in info[i][2:]:
            m[i][j-1]=j
time=0
dfs(0)
for i in xrange(n):
    print i+1,d[i],f[i]

Submission status: Wrong Answer

Solution code:
import sys

def dfs(i):
    global V, t, d, f

    if d[i] != 0:
        return

    d[i] = t
    t += 1
    for v in V[i]:
        dfs(v)

    f[i] = t
    t += 1

    return

lines = sys.stdin.readlines()
n = int(lines[0])
V = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    v = map(int, lines[i].split())
    V[v[0]] = v[2:]
d = [0] * (n + 1)
f = [0] * (n + 1)
t = 1

dfs(1)

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

Submission status: Wrong Answer

Solution code:
"""Depth First Search."""

n = int(input())

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

# searched or not, number of vertex, discovery time and finishing time
sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

def dfs(u):
    time = 0
    path.append(u)
    time += 1
    sndf[u].append(time)

    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not sndf[v][0]:
                time += 1
                sndf[v].append(time)
                path.append(v)
        else:
            path.pop()
            sndf[u][0] = True
            time += 1
            sndf[u].append(time)


dfs(1)

for x in sndf[1:]:
    print(*x[1:])

Submission status: Wrong Answer

Solution code:
"""Depth First Search."""

n = int(input())

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

# searched or not, number of vertex, discovery time and finishing time.
sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])
sndf.append(0)

path = []

time = 0

def dfs(u):
    global time
    path.append(u)
    time += 1
    sndf[u].append(time)

    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not sndf[v][0]:
                sndf[v][0] = True
                time += 1
                sndf[v].append(time)
                path.append(v)
        else:
            path.pop()
            sndf[u][0] = True
            time += 1
            sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:-1]:
    print(*x[1:])

Submission status: Wrong Answer

Solution code:
def DFS(G):
    ans = [0] + [[0,0,0] for _ in range(len(G))]
    def main(G,i):
        ans[0] += 1
        ans[i] = [i, ans[0], ans[0]]
        for j in sorted(G[i-1][2:]):
            if ans[j][0]==0: main(G,j)
        ans[0] += 1
        ans[i][2] = ans[0]
    main(G,1)
    return ans[1:]


if __name__=='__main__':
    n = int(input())
    G = [list(map(int,input().split())) for _ in range(n)]
    for out in DFS(G): print(*out)

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self,v):
        self.v = v
        self.c = []

def dfs(n,f,d,t,visited):
    f[n.v] = t
    t2 = t
    for c in sorted(n.c,key=lambda x:x.v):
        if not c in visited:
            t2 = dfs(c,f,d,t2+1,visited)
            visited.add(c)
    d[n.v] = t2+1
    return t2+1

n = int(raw_input())
nodes = {}
for _ in range(n):
    entry = map(int,raw_input().split(' '))
    nid = entry[0]
    if not nid in nodes: nodes[nid] = Node(nid)
    k = entry[1]
    if k > 0:
        children = entry[2:]
        for c in children:
            if not c in nodes: nodes[c] = Node(c)
            nodes[nid].c.append(nodes[c])

f = {}
d = {}
visited = set()
dfs(nodes[1],f,d,1,visited)
for k in f:
    print k,f[k],d[k]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

n = int(input())
a = [0]

for i in range(n):
    v = input().split()
    v.pop(0)
    v.pop(0)
    a.append([int(x) for x in v])

debug(a)
stack = [1]
results = [[0 for i in range(2)] for j in range(n + 1)]
results[0][0] = 0
time = 0


def depth_first_search(a, stack):
    debug(results)
    debug(stack)
    global time
    if len(stack) == 0:
        return

    v = stack.pop()
    if results[v][0] == 0:
        time += 1
        results[v][0] = time

    es = a[v]
    if len(es) == 0 and results[v][1] == 0:
        time += 1
        results[v][1] = time

    if len(es) != 0:
        stack.append(v)
        stack.append(es.pop(0))

    depth_first_search(a, stack)

depth_first_search(a, stack)
debug(results)

results.pop(0)

i = 1
for row in results:
    print(str(i) + " " + str(row[0]) + " " + str(row[1]))
    i += 1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf_8 -*-

level = False
def debug(v):
    if level:
        print(v)

n = int(input())
a = [0]

for i in range(n):
    v = input().split()
    v.pop(0)
    v.pop(0)
    a.append([int(x) for x in v])

debug(a)
stack = [1]
results = [[0 for i in range(2)] for j in range(n + 1)]
results[0][0] = 0
time = 0


def depth_first_search(a, stack):
    debug(a)
    debug(results)
    debug(stack)
    global time
    if len(stack) == 0:
        return

    v = stack.pop()
    if results[v][0] == 0:
        time += 1
        results[v][0] = time

    es = a[v]
    if len(es) == 0 and results[v][1] == 0:
        time += 1
        results[v][1] = time

    if len(es) != 0:
        stack.append(v)
        stack.append(es.pop(0))

    depth_first_search(a, stack)

for i in range(n):
    stack = [i + 1]
    depth_first_search(a, stack)

debug(results)

results.pop(0)

i = 1
for row in results:
    print(str(i) + " " + str(row[0]) + " " + str(row[1]))
    i += 1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(start_node_index):
    # init the first node
    v_index = int(start_node_index)
    vertex_visit_stack.append(v_index)
    vertex_color_list[v_index] = GRAY
    time = 1
    vertex_d_time[v_index] += time
    # init end
    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        try:
            next_vertex = adj_matrix[current_vertex - 1].index(1) + 1
        except ValueError:
            # print('err')
            vertex_visit_stack.pop()
            vertex_color_list[current_vertex] = BLACK
            time += 1
            vertex_f_time[current_vertex] += time
        else:
            if vertex_color_list[next_vertex] == WHITE:
                # print('w2g', current_vertex, next_vertex, vertex_color_list[next_vertex])
                vertex_color_list[next_vertex] = GRAY
                time += 1
                vertex_d_time[next_vertex] += time
                vertex_visit_stack.append(next_vertex)
                # node A to B only visit once
                adj_matrix[current_vertex - 1][next_vertex - 1] = 0
            else:
                time += 1
                vertex_f_time[current_vertex] += time
                vertex_visit_stack.pop()
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num

    vertex_visit_stack = [-1]
    vertex_color_list = [WHITE] * (vertex_num + 1)
    vertex_d_time, vertex_f_time = [0] * (vertex_num + 1), [0] * (vertex_num + 1)
    adj_matrix = generate_adj(vertex_info)

    graph_dfs(start_node_index=1)
    for i in range(vertex_num):
        print(i + 1, vertex_d_time[i + 1], vertex_f_time[i + 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = "BEFORE", "IN", "AFTER"


def generate_adj(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time
    # init the first node of overall graph iterations(times >= 1)
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    # init end
    while len(vertex_visit_stack) > 1:
        time += 1
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_next_vertex(node=current_vertex)
        # print(current_vertex, next_vertex, vertex_status_list, vertex_visit_stack)
        if next_vertex and vertex_status_list[next_vertex] is UNVISITED:
            vertex_status_list[next_vertex] = VISITED_IN_STACK
            vertex_d_time[next_vertex] += time
            vertex_visit_stack.append(next_vertex)

        else:
            other_vertex = get_next_vertex(current_vertex)
            if other_vertex:
                graph_dfs(other_vertex)
            else:
                vertex_visit_stack.pop()
                vertex_status_list[current_vertex] = POPPED_OUT
                vertex_f_time[current_vertex] += time

    return None


def get_next_vertex(node):
    for j in range(vertex_num):
        if adj_matrix[int(node) - 1][j]:
            adj_matrix[int(node) - 1][j] = 0
            return j + 1


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            # print('round', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num

    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, 'NULL')
    vertex_d_time, vertex_f_time = [[0] * (vertex_num + 1) for _ in range(2)]
    adj_matrix = generate_adj(vertex_info)

    time = 1
    dfs_start()

    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time
    # init the first node of overall graph iterations(times >= 1)
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    # init end
    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_next_vertex(node=current_vertex)
        # print(current_vertex, next_vertex, vertex_status_list, vertex_visit_stack)
        time += 1
        if next_vertex and vertex_status_list[next_vertex] is UNVISITED:
            # print('on', current_vertex, next_vertex)
            vertex_status_list[next_vertex] = VISITED_IN_STACK
            vertex_d_time[next_vertex] += time
            vertex_visit_stack.append(next_vertex)
        else:
            # other_vertex = get_next_vertex(current_vertex)
            # print('stuck', current_vertex, other_vertex)
            vertex_visit_stack.pop()
            vertex_status_list[current_vertex] = POPPED_OUT
            vertex_f_time[current_vertex] += time

    return None


def get_next_vertex(node):
    for j in range(vertex_num):
        if adj_matrix[int(node) - 1][j]:
            adj_matrix[int(node) - 1][j] = 0
            return j + 1


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            # print('round', i + 1)
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num
    # config length -> (vertex_num + 1)
    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, -1)
    vertex_d_time, vertex_f_time = ([0] * (vertex_num + 1) for _ in range(2))

    adj_matrix = generate_adj(vertex_info)

    time = 1
    dfs_start()

    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])

Submission status: Wrong Answer

Solution code:
from enum import Enum

class Dfs(object):
    """ Depth First Search """
    class Status(Enum):
        white = 1
        gray = 2
        black = 3

    def __init__(self, data):
        self.time = 0
        num_of_nodes = len(data)+1
        self.color = [Dfs.Status.white] * (num_of_nodes+1)
        self.S = []
        self.M = self._make_matrix(data)
        self.s_time = [0] * (len(data) + 1)
        self.f_time = [0] * (len(data) + 1)

    def _make_matrix(self, data):
        """ ??£??\??????????????? (M[i][j]?????¢??§??????????????????+1??????????????????????????????) """
        num = len(data)
        graph_table = [[0] * (num+1) for _ in range(num+1)]
        for d in data:
            node_id = d[0]
            num_of_e = d[1]
            for e in d[2:]:
                graph_table[node_id][e] = 1
        return graph_table

    def search(self, start):
        self.time += 1
        self.s_time[start] = self.time
        self.S.append(start)
        self.color[start] = Dfs.Status.gray

        while self.S:
            u = self.S[-1]
            v = self.next(u)
            if v != None:
                if self.color[v] == Dfs.Status.white:
                    self.color[v] = Dfs.Status.gray
                    self.time += 1
                    self.s_time[v] = self.time
                    self.S.append((v))
            else:
                self.S = self.S[:-1]
                self.color[u] = Dfs.Status.black
                self.time += 1
                self.f_time[u] = self.time

    def next(self, node):
        """ ?¬?????¨???????????±???????????????????????????????????????????????¨??????????????????????????????? """
        edges = self.M[node]
        for i in range(1, len(edges)):
            if edges[i] == 1:
                if self.color[i] == Dfs.Status.white:
                    return i
        return None

    def print(self):
        for r in self.M:
            print(*r)



if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for _ in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????????
    d = Dfs(data)
    # d.print()
    d.search(1)

    # ???????????????
    for i in range(1, num+1):
        print('{0} {1} {2}'.format(i, d.s_time[i], d.f_time[i]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""

input:
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

output:
1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6

"""
import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def dfs(v_init):
    global timer

    # init the first node of overall graph iterations(times >= 1)
    stack = list()
    stack.append(v_init)
    d_time[v_init] += timer
    # init end

    while stack:
        current = stack[-1]
        v_table = adj_table[current]
        visited[current] = VISITED_IN_STACK
        # if adj is None, current's adj(s) have been all visited
        adj = v_table.pop() if v_table else None

        if adj:
            if visited[adj] is UNVISITED:
                visited[adj] = VISITED_IN_STACK
                timer += 1
                d_time[adj] += timer
                stack.append(adj)
        else:
            stack.pop()
            visited[current] = POPPED_OUT
            timer += 1
            f_time[current] += timer

    return None


def dfs_init():
    global timer
    for v in range(v_num):
        if visited[v + 1] == UNVISITED:
            dfs(v + 1)
            timer += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    vertices = map(lambda x: x.split(), _input[1:])

    # config length = (v_num + 1)
    # stack = []
    visited = [UNVISITED] * (v_num + 1)
    d_time, f_time = ([0] * (v_num + 1) for _ in range(2))
    adj_table = tuple([] for _ in range(v_num + 1))
    for v_info in vertices:
        v_index, adj_num, *adj_list = map(int, v_info)
        # assert len(adj_list) == adj_num
        adj_table[v_index].extend(sorted(adj_list, reverse=True))

    # timing start from 1
    timer = 0
    dfs_init()

    for index, time_info in enumerate(zip(d_time[1:], f_time[1:]), 1):
        print(index, *time_info)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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


if __name__ == '__main__':
    N = int(input())
    matrix = [[0] * N for _ in range(N)]
    color = [0] * N
    for i in matrix:
        node_info = [int(i) for i in input().split()]
        node_i = node_info[0] - 1
        if not node_info[1] == 0:
            for i in node_info[2:]:
                matrix[node_i][i - 1] = 1
    colors = [0] * len(matrix)
    detect_time = [0] * len(matrix)
    finished_time = [0] * len(matrix)
    time = 0
    for i, val in enumerate(colors):
        if val == 0:
            time = dfs(i, colors, matrix, time, detect_time, finished_time)

    for i in range(len(matrix)):
        print('{} {} {}'.format(i + 1, detect_time[i], finished_time[i]))

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

time = 0

def dfs(u, adj, d, f, sumi):
    global time
    time += 1
    d[u] = time

    for v in adj[u]:
        if v not in sumi:
            dfs(v, adj, d, f, sumi)
        sumi.add(v)

    time += 1

    f[u] = time


def solve():
    n = int(input())
    adj = [None] * n

    for i in range(n):
        u, k, *vs = [int(j) - 1 for j in input().split()]
        # debug(vs, locals())
        adj[u] = vs

    # debug(adj, locals())
    
    d = [0] * n
    f = [0] * n
    sumi = {0}

    dfs(0, adj, d, f, sumi)

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

    pass

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

time = 0

def dfs(u, adj, d, f, sumi):
    global time
    time += 1
    d[u] = time

    for v in adj[u]:
        if v not in sumi:
            dfs(v, adj, d, f, sumi)
        sumi.add(v)

    time += 1

    f[u] = time


def solve():
    n = int(input())
    adj = [None] * n

    for i in range(n):
        u, k, *vs = [int(j) - 1 for j in input().split()]
        # debug(vs, locals())
        adj[u] = vs

    # debug(adj, locals())
    
    d = [0] * n
    f = [0] * n
    sumi = {0}

    dfs(0, adj, d, f, sumi)

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

    pass

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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


n = int(input())

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

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

dfs(0)

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

Submission status: Wrong Answer

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


n = int(input())

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

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

dfs_recursive(0)

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

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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


n = int(input())

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

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

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

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

Submission status: Wrong Answer

Solution code:
# ??????????????????????£?????????????deque??????????????????
from collections import deque


class Node:
    def __init__(self, no, childs):
        self.no = no
        self.childs = childs
        self.find_time = None
        self.finish_time = None
        self.visit = False


def get_node_index(nodes, no):
    for i in range(len(nodes)):
        if nodes[i].no == no:
            return i


def get_unvisited(visited, childs):

    if childs is None: return None

    for i in range(len(childs)):
        if childs[i] not in visited:
            return childs[i]


"""
Main??????????????????
"""
# Node??°?????????
N = int(input())

# Node??????????????????????????????
nodes = []

# Node??????????¨????
for i in range(N):
    j = list(map(int, input().split())) # ??\??????????§£
    no = j[0]                           # Node??????????????? [2 2 1 4] ->2?????????
    childNum = j[1]
    if childNum != 0:
        childs = j[2:]                  # ??????????´?????????? [2 2 1 4] ->[1,4]?????????
    else:
        childs = []                     # ??????????´?????????? [2 2 1 4] ->[1,4]?????????
    nodes.append(Node(no, childs))


# ??±???????????¢?´¢(DFS)?????????
total_time = 1   # ??¢?´¢??????
stack = deque() # ??¢?´¢???????´?????´?????????????
stack.appendleft(1)
no = get_node_index(nodes, stack[0])  # ?????¨??¢?´¢???????´???????
nodes[no].find_time = total_time
visited = []    # ??¢?´¢??????????´?????´??????????

while stack:
    no = get_node_index(nodes, stack[0])  # ?????¨??¢?´¢???????´???????
    total_time += 1  # ??¢?´¢??????+1
    visited.append(stack[0])              # ??¢?´¢??????????????????????´?
    # ?????¢?´¢???????´??????????
    unvisited = get_unvisited(visited, nodes[no].childs)
    if unvisited is not None:
        # ?????¢?´¢???????´??????????????????????????????¢?´¢????´????????????§??????????????????????????????????´???§????????´????????¢?´¢?????\?????????????????????
        if nodes[unvisited-1].visit is False:
            nodes[unvisited-1].visit = True
            stack.appendleft(unvisited)
            nodes[unvisited-1].find_time = total_time
    else:
        stack.popleft()
        nodes[no].finish_time = total_time



#??¨?????????
for i in range(N):
    print("{0} {1} {2}".format(nodes[i].no, nodes[i].find_time, nodes[i].finish_time))

Submission status: Wrong Answer

Solution code:
G = {}
for _ in range(int(input())):
  x = list(map(int, input().split()))
  G[x[0]] = sorted(x[2:])

t = 1
stack = [1]
timestamp = {1:[t]}

while len(stack) > 0:
  t += 1
  v = stack[-1]

  while len(G[v]) > 0:
    v = G[v].pop(0)
    if v in timestamp: continue
    stack.append(v)
    timestamp[v] = [t]
    break
  else:
    v = stack.pop()
    timestamp[v].append(t)

for i in timestamp:
  print(i, *timestamp[i])