Keys and Rooms Problem

Keys and Rooms Problem — ExecCode Hard DSA Practice

Solve the Keys and Rooms problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description Problem You are in a building with N rooms, labeled 0 to N-1. Each room may contain keys to other rooms. You start in room 0 and can use any keys you find to visit other rooms. Determine whether you can visit every room at least once. Input Format The input is given as lines representing the list of keys in each room. Each line i (starting from 0) contains zero or more integers separated by spaces: the labels of rooms for which room i contains keys. The number of lines equals N, the total number of rooms. Example input for N=4 with room contents listed line-by-line: room0keysline room1keysline room2keysline room3keysline Output Format Output a single line containing true if every room is reachable starting from room 0 (using keys found along the way), otherwise output false. Constraints 1 <= N <= 1000 (N is the number of input lines) - Each key is an integer in the range [0, N-1] - Keys may repeat or reference the same room multiple times - Do not assume any particular ordering of keys on a line

Examples

Input {"data": "4\n1\n2\n3"}; Output true. Input {"data": "4\n1 3\n3 0 1\n2\n0"}; Output false. Input {"rooms": [[1], [2], [3], []]}; Output true

Constraints

1<=N<=10^5

Practice Keys and Rooms free on ExecCode. Browse DSA problems, topic map, and placement guides.