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:
from collections import defaultdict

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

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

Submission status: Wrong Answer

Solution code:
j = 1
def dfs(graph, start, result, visited=None):
    global j
    if visited == None:
        visited = []
    visited.append(start)
    result[start][1]  = j
    for next in graph[start][2:]:
        if next in visited:
            continue
        j += 1
        dfs(graph, next, result, visited)
    else:
        j += 1
        result[start][2] = j

n = int(input())
g = [[]]
r = [[i,0,0] for i in range(n + 1)]

for i in range(n):
    g.append(list(map(int, input().split())))
dfs(g,1,r)
for i in range(1,n+1):
    print(*r[i])

Submission status: Wrong Answer

Solution code:
j = 1

def dfs(graph, start, result, visited=None):
    global j
    if visited == None:
        visited = []
    visited.append(start)
    result[start][1]  = j
    for next in graph[start][2:]:
        if next in visited:
            continue
        j += 1
        dfs(graph, next, result, visited)
    else:
        j += 1
        result[start][2] = j

n = int(input())
g = [[]]
r = [[i,0,0] for i in range(n + 1)]
v = []

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


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

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

Submission status: Wrong Answer

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

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

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

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

#print(edge)

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

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

discover[0]=1
dfs(0,2)

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
from collections import deque
#入力値の整理
n = int(input())
adj={}
visited={}
d={}
f={}
t=0
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
  visited[u] = False
  d[u] = -1
  f[u] = -1

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

while True:
  t = t+1
  clear = True
  while adj[v]:
    cand = adj[v].popleft()
    if not visited[cand]:
      next = cand
      d[cand] = t + 1
      visited[cand] = True
      clear = False
      break
  if clear:
    f[v] = t + 1
    if stack:
      next = stack.pop()
      v = next
    else:
      break
  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: Wrong Answer

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
    
    dfs(0)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

global time
time = 0


def dfs(graph, start,explored,discover,finish):
    if start == []:
        explored.append(start)
        return
    else:
        if start not in explored:
            global time
            time = time + 1
            discover[start-1] = time
        neighbours = graph[start]
        while len(neighbours) > 0:
            neighbour = neighbours.pop(0)
            dfs(graph,neighbour,explored,discover,finish)
        if start not in explored:
            time = time + 1
            finish[start - 1] = time
        explored.append(start)

def main():


    d = [0]*6
    f = [0]*6

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

    g = {}

    d = [-1]*n

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


    exp = []

    dfs(g,1,exp,d,f)


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

main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

global time
time = 0

def dfs(graph,start,explored,discover,finish):
    if start == []:
        explored.append(start)
        return
    else:
        if start not in explored:
            global time
            time = time + 1
            discover[start-1] = time

        neighbours = graph[start]
        while len(neighbours) > 0:
            neighbour = neighbours.pop(0)
            if neighbour != start:
                dfs(graph,neighbour,explored,discover,finish)
        if start not in explored:
            time = time + 1
            finish[start - 1] = time
        explored.append(start)

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

    d = [0]*6
    f = [0]*6

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

    g = {}

    d = [-1]*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 = []

    for node in all_vertex:
     if node not in exp:
        dfs(g,node,exp,d,f)



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

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
    dfs(1)
    for i in range(1, n + 1):
        print(" ".join(map(str, ans[i])))
MAIN()

Submission status: Wrong Answer

Solution code:
n = int(input())

m = [[0 for i in range(n)] for j in range(n)]

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

color = ["white" for i in range(n)]

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

def dfs(u):
    global time
    time += 1
    color[u] = "gray"
    d[u] = time
    for i in range(u, n):
        if m[u][i] and color[i] == "white":
            dfs(i)
    color[u] = "black"
    time += 1
    f[u] = time

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

Submission status: Wrong Answer

Solution code:
n = int(input())

m = [[0 for i in range(n)] for j in range(n)]

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

color = ["white" for i in range(n)]

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

def dfs(u):
    global time
    time += 1
    color[u] = "gray"
    d[u] = time
    for i in range(n):
        if m[u][i] and color[i] == "white":
            dfs(i)
    color[u] = "black"
    time += 1
    f[u] = time

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [[0 for j in range(n)] for i in range(n)]
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

hist_stack = [0]
time_hist = [0]

vert_hist = [[] for i in range(n)]
vert_hist[0].append(1)
time = 2
while True:
    flag = False
    if len(hist_stack) == 0: break
    for j in range(n):
        if A[hist_stack[-1]][j] == 1 and j not in time_hist:
            hist_stack.append(j)
            time_hist.append(j)
            vert_hist[j].append(time)
            flag = True
            break
    if not flag:
        j = hist_stack.pop()
        time_hist.append(j)
        vert_hist[j].append(time)
    time += 1

for i in range(n):
    print(i+1, ' '.join(list(map(str, vert_hist[i]))))

Submission status: Wrong Answer

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 i in range(n):
    print(i+1, d[i], f[i])

Submission status: Wrong Answer

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):
        stack = [(1, 0)]
        visited = []
        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: Wrong Answer

Solution code:
class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}
        self.color = 'white'
        self.dist =10000000
        self.pred = None
        self.disc = 0
        self.fin = 0
    
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    def setColor(self,color):
        self.color = color

    def setDistance(self,d):
        self.dist = d

    def setPred(self,p):
        self.pred = p

    def setDiscovery(self,dtime):
        self.disc = dtime
        
    def setFinish(self,ftime):
        self.fin = ftime
        
    def getFinish(self):
        return self.fin
        
    def getDiscovery(self):
        return self.disc
        
    def getPred(self):
        return self.pred
        
    def getDistance(self):
        return self.dist
        
    def getColor(self):
        return self.color

    def getConnections(self):
        return self.connectedTo.keys()

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getId(self):
        return self.id


class Graph:
    def __init__(self):
        self.vertList = {}
        self.costList={}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertlist.keys()

    def __iter__(self):
        return iter(self.vertList.values())


class DFSGraph(Graph):
	def __init__(self):
		super().__init__()
		self.time = 0

	def dfs(self):
		for aVertex in self:
			aVertex.setColor('white')
			aVertex.setPred(-1)
		for aVertex in self:
			if aVertex.getColor() == 'white':
				self.dfsvisit(aVertex)

	def dfsvisit(self,startVertex):

		for aVertex in self:
			aVertex.setColor('white')
			aVertex.setPred(-1)

		startVertex.setColor('gray')
		self.time += 1
		startVertex.setDiscovery(self.time)
		for nextVertex in startVertex.getConnections():
			if nextVertex.getColor() == 'white':
				nextVertex.setPred(startVertex)
				self.dfsvisit(nextVertex)
		startVertex.setColor('black')
		self.time += 1
		startVertex.setFinish(self.time)

Submission status: Wrong Answer

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 = [1] * n
finish_time = [0] * n
is_visit = [False] * n
stack = [1]
time = 1

while(len(stack) != 0):
    time += 1
    now = stack[-1] - 1
    if len(input_line[now]) == 0:
        finish_time[stack.pop()-1] = time
    else:
        detect = input_line[now].pop(0)
        if is_visit[detect-1]:
            finish_time[stack.pop()-1] = time
            continue
        stack.append(detect)
        detect_time[detect-1] = time
        is_visit[detect-1] = True

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

Submission status: Wrong Answer

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)
    dfs(g, 0, 1)
    for i in range(n):
        print(i, d[i], f[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)
    dfs(g, 0, 1)
    for i in range(n):
        print(i+1, d[i], f[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    dfs(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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:
        f[x-1] = t
    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):
    print(i+1, d[i], f[i])

Submission status: Wrong Answer

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):
    print(i+1, d[i], f[i])

Submission status: Wrong Answer

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 f[now-1] != 0: t -= 1
    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")
                dfs(G, d, f, i)
            else:
                print("end of branch")
            
        t += 1
        if f[now-1] == 0:
            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

dfs(N, d, f, 1)

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

Submission status: Wrong Answer

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 f[now-1] != 0: t -= 1
    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")
                dfs(G, d, f, i)
            
        t += 1
        if f[now-1] == 0:
            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

dfs(N, d, f, 1)

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

Submission status: Wrong Answer

Solution code:
n=0
t=2
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
    for (j,x) in enumerate(array[i]):
        if x == 1:
            d[j] = t
            t += 1
            dfs(array,j,d,f)
    f[i] = t
    t += 1
    return 


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
d[0]=1
stack+=[1]
check+=[-1]

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

           ## print("stack:",stack)
           ## 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)
            


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

Submission status: Wrong Answer

Solution code:
n=int(input())

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

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

time=1


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

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

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

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


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

Submission status: Wrong Answer

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
while True:
	count+=1
	p=0
	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
	if p is 1:
		for i in range(n):
			ls[i][stuck[len(stuck)-1]]=0

	if p is 0:
		#print("//")
		a=stuck.pop()
		f[a]=count
		for i in range(n):
			ls[a][i]=0

	if len(stuck) is 0:
		#print("break")
		break

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

Submission status: Wrong Answer

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
while True:
	count+=1
	p=0
	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

	if p is 1:
		for i in range(n):
			ls[i][stuck[len(stuck)-1]]=0
	if p is 0:
		#print("//")
		a=stuck.pop()
		f[a]=count
		for i in range(n):
			ls[a][i]=0

	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")

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

Submission status: Wrong Answer

Solution code:
def dfs(adj, s, d, f, now):
    now += 1
    d[s] = now
    for t in adj[s]:
        if f[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)]
d, f, _ = dfs(adj, 0, d, f, 0)

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

Submission status: Wrong Answer

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)
print(next)
time=1
d=[0 for i in range(n)]
f=[0 for i in range(n)]
while(len(stk)!=0):
	if len(next[stk[-1]])==0:
		if d[stk[-1]]==0:
			d[stk[-1]]=time
			#print(stk[-1])
			time+=1
		f[stk[-1]]=time
		#print(stk[-1])
		time+=1
		stk.pop()
	else:
		v=min(next[stk[-1]])
		if d[v]!=0:
			next[stk[-1]].remove(v)
		else:
			if d[stk[-1]]==0:
				d[stk[-1]]=time
				time+=1
			#print(stk[-1])
			next[stk[-1]].remove(v)
			stk.append(v)
			

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

Submission status: Wrong Answer

Solution code:
n=0
t=2
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):
            for (j,x) in enumerate(array[i]):
                if x == 1:
                    d[j] = t
                    t += 1
                    dfs(array,j,d,f)
            f[i] = t
            t += 1
    return dfs(array,i+1,d,f)


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

if __name__ == "__main__":
    main()