EPIC1304 - Graph Cycle Detection
In a graph of nodes & directed edges, a loop is defined as a path whereby you can follow the edges and arrive back at the starting point. For example, in this graph there is a loop of three nodes (A, C, D). B is not part of the loop.
This graph is encoded as:
A-C
C-D
D-A
Given a directed graph, return an alphabetized list of all nodes that participate in a loop. In this example, the correct answer is ACD. You will be given at most 26 nodes (A through Z).
Input
A graph encoding of nodes and directed edges.
Output
The alphabetized list of all nodes that participate in a loop. (Must be returned in uppercase)
Example
Input: A-C
C-D
D-A Output: ACD
hide comments
omar:
2017-12-20 22:20:13
Weak test cases;
|
|
suraj_:
2016-10-17 19:51:37
good question. little tricky. finally AC. |
|
avisheksanvas:
2016-08-10 18:26:47
EASY!
|
|
raj:
2015-04-19 16:18:07
CAN SOMEONE TELL ME HOW TO TERMINATE THE INPUT IN C....... |
|
Maulik Soneji:
2014-12-16 19:50:13
Thanks to the comments by @yellow_submarine, i got this right.
|
|
yellow_submarine:
2014-10-16 10:45:53
Yes, if there are multiple cycles you have to print them all, for ex if a digraph has following cycles: A-X-C-B-A and R-S-W-R then output is ABCRSWX Last edit: 2014-10-16 10:46:16 |
|
Kishlay Raj:
2014-09-04 11:51:28
can there be more than one loop in question or anything such as nested loop
|
|
grind:
2014-06-17 20:43:02
how will the number of input characters will be decided?
|
|
Rana Saha:
2014-03-08 21:11:00
Can the given Graph contain more than one cycle ?
|
Added by: | BYU Admin |
Date: | 2013-03-20 |
Time limit: | 3s-10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |