Samarth and Soham decide to have another shot at the Tour de France. This time there...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Samarth and Soham decide to have another shot at the Tour de France. This time there are various checkpoints on the roads in Paris. All the roads are 2-way. After cycling for 10 hours Samarth realizes that they have cycled past the Eiffel Tower too many times. Soham then exclaims, we have been cycling in cycles. Soham now wants to find out how many simple cycles exist, but Samarth wants to find out which checkpoints are part of these cycles. Can you help them figure this out and reach the finish. A simple cycle is a path(at least one road) from a checkpoint to itself visiting other checkpoints atmost once such that no subset of the checkpoints can form a cycle themselves. • Input First line of input consists of two integers N and M which denote the number of checkpoints and the number of roads respectively. The next 2 lines consist of two arrays A and B of size M, which means that there is a road between checkpoint A[i] and B[i] for every 1 ≤ i ≤ M • Output Output the number of simple cycles. In the next line output N integers which are either 1 or 0 such that 1 at ith position indicates that ith checkpoint is a part of one or more cycles, whereas 0 indicates that it is part of no cycles. Constraints 0 1 ≤N ≤ 105 0 0 ≤M ≤ min(N * (N − 1)/2, 105) o 1 ≤ A[i], B[i] ≤ N Vi € [1, N] • Sample Input 1 8 10 1 1 1 7 7 5 8 2 26 2 3 4 1 5 6 4 3 77 • Sample Output 1 3 1 1 1 0 1 1 1 0 • Sample Input 2 77 1 3 3 2 6 5 2 2 2 4 5 5 7 4 • Sample Output 2 1 0 1 1 1 0 0 0 Explanation of Input 1 The map of Paris of Input 1 looks as follows 8 7 3 2 Here there are 3 simple cycles viz. {1,2,3}, {1,2,7}, {5,6,7} Here all checkpoints except 4 and 8 are part of cycles Samarth and Soham decide to have another shot at the Tour de France. This time there are various checkpoints on the roads in Paris. All the roads are 2-way. After cycling for 10 hours Samarth realizes that they have cycled past the Eiffel Tower too many times. Soham then exclaims, we have been cycling in cycles. Soham now wants to find out how many simple cycles exist, but Samarth wants to find out which checkpoints are part of these cycles. Can you help them figure this out and reach the finish. A simple cycle is a path(at least one road) from a checkpoint to itself visiting other checkpoints atmost once such that no subset of the checkpoints can form a cycle themselves. • Input First line of input consists of two integers N and M which denote the number of checkpoints and the number of roads respectively. The next 2 lines consist of two arrays A and B of size M, which means that there is a road between checkpoint A[i] and B[i] for every 1 ≤ i ≤ M • Output Output the number of simple cycles. In the next line output N integers which are either 1 or 0 such that 1 at ith position indicates that ith checkpoint is a part of one or more cycles, whereas 0 indicates that it is part of no cycles. Constraints 0 1 ≤N ≤ 105 0 0 ≤M ≤ min(N * (N − 1)/2, 105) o 1 ≤ A[i], B[i] ≤ N Vi € [1, N] • Sample Input 1 8 10 1 1 1 7 7 5 8 2 26 2 3 4 1 5 6 4 3 77 • Sample Output 1 3 1 1 1 0 1 1 1 0 • Sample Input 2 77 1 3 3 2 6 5 2 2 2 4 5 5 7 4 • Sample Output 2 1 0 1 1 1 0 0 0 Explanation of Input 1 The map of Paris of Input 1 looks as follows 8 7 3 2 Here there are 3 simple cycles viz. {1,2,3}, {1,2,7}, {5,6,7} Here all checkpoints except 4 and 8 are part of cycles
Expert Answer:
Answer rating: 100% (QA)
Samarth and Soham decide to have another shot at the Tour de France This time there are various chec... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
A car of mass 1 3 0 1 kg , is initially travelling at 2 1 . 3 ms - 1 . Calculate the kinetic energy of the vehicle in kJ to the nearest whole number.
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
We will be working with a company called Global Bike Inc., (GBI). Information regarding GBI follows. Company History Global Bike Inc. has a pragmatic design philosophy that comes from its deep roots...
-
O An hair dryer is basically a duct with a fan that draws cool air from the atmosphere at one end, forces it on an electrical resistor (where the air is heated up) and discharges it at the other end....
-
Just like the Olympics, the World Cup comes around only every four years. And just like the Olympics, the athletes prepare as only elite athletes know how to do. France's highly regarded national...
-
Wanda is a 20 percent owner of Video Associates, which is treated as a pass through entity for federal income tax purposes. This year, Wanda was allocated $45,000 of ordinary income from Video...
-
In a survey, U.S. adults were asked to identify which social media platforms they use. The results are shown in the figure. Six adults who participated in the survey are randomly selected and asked...
-
Two automatic systems for dispensing maps are being compared by the state highway department. The accompanying breakeven chart of the comparison of these systems (System I vs System II) shows total...
-
Over the course of the semester, we covered a clear and effective 10 Step process for developing a strategy as described in the Inspired. Logical. Strategy That Works book. Please bullet point the 10...
-
Gourmet Coffee (GC) is a specialty coffee shop that sells roasted coffee beans. It buys green beans, roasts them in its shop, and then sells them to the consumer. GC estimates that it sells about...
-
When Starling, Inc. manufactured 40,000 units, the total variable cost was $115,200. What would the total variable cost be when 54,000 units are manufactured? Calculate.
-
1. Strongest Motivations for Fashion to Acquire Flavoring : Fashion Inc. has several compelling reasons to consider acquiring Flavoring International: Earnings Growth : Flavorings earnings growth...
-
Margaret Thatcher uses gas to heat her home and has collected data on her monthly gas bill and monthly heating degree-days. The heating degree-days for a month are calculated by subtracting 65 from...
-
Problem 1 Denise Ondeyko, CPA, is drafting an audit program to test controls over the Purdue Corporation's cost records: Required: 1 . Explain the importance of determining the disposition of...
-
Tax Analysis Homework Content Requirements Most entrepreneurs have great ideas and understand the technology and design that goes into making a new product but often do not have a background in...
-
Certainly! Lets analyze the information provided: .RDTOH Balance at Year-End : Total RDTOH balance: $17,000 Eligible portion: $10,000 Non-eligible portion: $7,000 .Taxable Dividends Paid During the...
-
Correctly label the components of the respiratory system. Pharynx Nasal cavity Hard palate Nostril Larynx Epiglottis Posterior nasal aperture re to search PA) pll 14 O B F6 $5 36 < Prev 1 of 25 DELL...
-
Data 9.2 on page 540 introduces the dataset Cereal, which includes information on the number of grams of fiber in a serving for 30 different breakfast cereals. The cereals come from three different...
-
How has human resource managements evolution over the years helped to make it a better partner to the business? In what way would you expect HRM to continue to evolve over the years?
-
Your companys founder believes that younger workers are more energetic and serve better in sales positions. Before posting a new job ad for your sales division, he recommends that you list an age...
-
What is organizational change?
-
What is the pressure drop associated with water at \(27^{\circ} \mathrm{C}\) flowing with a mean velocity of \(0.1 \mathrm{~m} / \mathrm{s}\) through an \(800-\mathrm{m}-\) long cast iron pipe of...
-
Fully developed conditions are known to exist for water flowing through a \(50-\mathrm{mm}\)-diameter tube at \(0.02 \mathrm{~kg} / \mathrm{s}\) and \(27^{\circ} \mathrm{C}\). What is the maximum...
-
Water at \(35^{\circ} \mathrm{C}\) is pumped through a horizontal, \(200-\mathrm{m}\)-long, \(30-\mathrm{mm}\)-diameter tube at \(0.25 \mathrm{~kg} / \mathrm{s}\). Over time, a 2-mm-thick layer of...
Study smarter with the SolutionInn App