Topological Order Or Cycle
Programming Interview
Hard
4 views
Problem Description
For each testcase you get a directed graph. If topological order exists, output one order. If cycle exists, output CYCLE.
Input Format
First integer t. For each: n m then m edges u v (u->v).
Output Format
t lines: order or CYCLE.
Sample Test Case
Input:
2
4 3
1 2
1 3
3 4
3 3
1 2
2 3
3 1
Constraints
Sum of n+m over all testcases
Official Solution
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it)); m=int(next(it))
g=[[] for _ in range(n+1)]
indeg=[0]*(n+1)
for i in range(m):
u=int(next(it)); v=int(next(it))
g[u].append(v)
indeg[v]+=1
q=deque([i for i in range(1,n+1) if indeg[i]==0])
order=[]
while q:
u=q.popleft()
order.append(u)
for v in g[u]:
indeg[v]-=1
if indeg[v]==0:
q.append(v)
if len(order)!=n:
out.append('CYCLE')
else:
out.append(' '.join(map(str,order)))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!