EPIC1304 - Graph Cycle Detection

no tags 

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;
A-B
B-C
C-A
B-D
D-E
E-C
answer: ABCDE

suraj_: 2016-10-17 19:51:37

good question. little tricky. finally AC.

avisheksanvas: 2016-08-10 18:26:47

EASY!
@rajma996 Use scanf("%s",&s) != EOF.

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.
But it should be specified in the problem as well.

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?
there is no number .. how to se that the input has ended

Rana Saha: 2014-03-08 21:11:00

Can the given Graph contain more than one cycle ?
If Yes, Are we supposed to print all of them ?

Last edit: 2014-03-08 21:11:15

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