All Tracks Algorithms Graphs Strongly Connected Components Problem

Removing Errors in Genomes!
Tag(s):

Backtracking, DFS, Graph Theory, Medium-Hard, StronglyConnectedComponenets

Problem
Editorial
Analytics

Pradyumn was studying Genome Sequencing from Professor Michael Levin. Professor Michael said to him "In real world, things are lot nasty for sequencing genomes. Many errors are there in extracted genomes. No fool - proof technique is till now made for extracting error - free reads(substrings of original genome) from which Genome can be constructed. We have to create graph from strings. Graph constructed from strings have many tips and bubbles(errors of reads which constructs wrong graph). Here we are taking Tip Removal into consideration and neglecting Bubble Removal part. Suppose you are given set of reads. You constructed following graph according to them. You don’t need hanging parts in the graphs. You just need one main big main loop. According to graph given below, you need only AA – AC – CG – GT – TT – TG – GC – CA – AA. According to Tip Removal Process all the hanging parts of the graph are removed. It is made sure that the size of big loop is always greater than the hanging parts. "Graph Suppose your reads are
AACG
AAGG
ACGT
CAAC
CGTT
GCAA
GTTG
TCCA
TGCA
TTGC
To construct above graph. You will take 2 length substring from left to right of any read. And make directed edge from node of left substring to right substring. And between any two node only one unique edge exists. Example,
Now if we remove the tips, and compile the graph we will get Genome : AACGTTGCC
You can check all the substrings at the nodes of graph can be constructed by this genomes. In this way, we remove errors from reads to construct Error - Free Genome. Note that Genomes are cyclic, so if you are wandering for edge from CA to AA. Check the last letter and first letter of Genome(try it yourself). Pradyumn is still confused as I think most of you will be.
Now, interesting part is here. Professor Michael knows that these things can not be understood so easily. So, he added in his statement “I will give you a graph in input, you will not need to construct graph from reads(strings). Now, you need to tell me which nodes are remaining after removing all the tips from graph. As many sequences are possible. You need to sort the nodes according to their index and give your output. ” For above example. Output is "1 2 3 4 5 6 7 8".
NOTE: Hanging Parts consist of line and loops Such that no two lines or two loops are interconnected. A single hanging line or loop is connected by single node of big loop, conversely, only one edge connects a hanging part with the big main loop.

INPUT CONSTRAINTS
\(1 \le n \le 10^5\)
\(1 \le m \le 10^6\)
\(1 \le u, v \le 10^5\)

INPUT FORMAT
Two space separated integers n and m , where n denotes number of nodes in the graph and m denoted number of directed edges in the graph
Next m lines contain two space separted integers u and v, which depicts there is an directed edge from u to v(u -> v).
OUTPUT FORMAT
Order of vertices in non – decreasing order of the graph, after removal of tips.

SAMPLE INPUT
12 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 9
9 10
12 11
11 8
SAMPLE OUTPUT
1 2 3 4 5 6 7 8
Explanation

Already discussed above.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

The LNM Institute of Information Technology

Challenge Name

LNMIIT Algorithms Cup - June 2017

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?