Round Trip 2

Task:

Byteland has $n$ cities and $m$ flight connections. Your task is to design a round trip that begins in a city, goes through one or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers $n$ and $m$: the number of cities and flights. The cities are numbered $1,2,\dots,n$.

Then, there are $m$ lines describing the flights. Each line has two integers $a$ and $b$: there is a flight connection from city $a$ to city $b$. All connections are one-way flights from a city to another city.

Output

First print an integer $k$: the number of cities on the route. Then print $k$ cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

• $1 \le n \le 10^5$
  
• $1 \le m \le 2 \cdot 10^5$
  
• $1 \le a,b \le n$
  

Solutions:

It's quite similar with Round Trip, so I think that's reason why its called Round Trip 2. The only difference is that It has directed edges. Therefore, we no longer need to take previously vertex into consideration. Because if it has a directed edge that connect to parent vertex, then it constructs a cyclic path. However, instead of 2 states ( visited or unvisited), now we have 3 states and there are unvisited,processing and unvisited. The unvisited state represents the vertex that DFS hasn't accessed yet. By contrast, the visited state shows that the vertex is accessed then exited. Lastly, the processing state means that current vertex is being processed.
Implementation:

 1from collections import defaultdict
 2import sys
 3sys.setrecursionlimit(9**9)
 4def dfs(node,graph,state,parent):
 5    for i in graph[node]:
 6        parent[i]=node
 7
 8        # when reaching the processing vertex, it means that cyclic path is existed. 
 9        # so returning the start vertex of cyclic path.
10        if state[i]==0:
11            return i
12
13        # skipping visited vertex
14        if state[i]==1:
15            continue
16        state[i]=0
17        start= dfs(i,graph,state,parent)
18        if start>0:
19            return start
20        state[i]=1
21    return 0
22
23def main():
24    n,m = map(int,input().strip().split())
25    graph=defaultdict(list)
26
27    for i in range(m):
28        u,v=map(int,input().strip().split())
29        graph[u].append(v)
30
31    # constructing a state array which has -1 for unvisited, 1 for visited, and 0 for processing
32    state=[-1]*(n+1)
33    parent=[-1]*(n+1)
34    start=0
35    for i in range(1,n+1):
36
37        # skipping every visited vertex
38        if state[i]==-1:
39            state[i]=0
40            start=dfs(i,graph,state,parent)
41            if start>0:
42                break
43            state[i]=1
44    if start==0:
45        print("IMPOSSIBLE")
46    else:
47        res=[]
48        res.append(str(start))
49        tmp=parent[start]
50        while tmp!=start:
51            res.append(str(tmp))
52            tmp=parent[tmp]
53        res.append(str(start))
54        print(len(res))
55        print(" ".join(res[::-1]))
56main()
57 

Time complexity: With DFS, the time complexity definitely is $O(N)$.

Space complexity: By tracking the state of vertex, so we have $O(N)$ for space complexity where N is the number of vertexes.