Unreachable Functions
InterviewTime limit1sMemory limit128 MB
Given a control flow graph built from three instruction types with fall-through or jump edges, count how many functions are unreachable from the first one.
- Level
Easy3 of 10
- Topics
- Graph, BFS, Implementation
- Solved
- No attempts yet
Problem
When analyzing source code in a programming language, it can be useful to know whether some functions will never execute. Such functions may indicate an error in the code.
In this problem, we consider a simple programming language made only of the following kinds of functions.
RADI: execution continues with the next function.IDI a: execution moves to thea-th function.IDI a ILI b: execution moves to either thea-th or theb-th function.
The program always starts at the first function.
Write a program that calculates how many functions will never execute.
Input
Each line of input contains one function. The i-th line contains the i-th function.
After the last function, the next line contains a period .. This line is not part of the program and is not counted as a function.
The number of functions is at most 10,000.
Output
Print one line containing the number of functions that will never execute.