Опыт собеседования с National Instruments | Комплект 2
Межпланетная торговля:
Хобер Мэллоу хочет наладить межгалактическую торговлю, которая позволила бы торговать между разными планетами. На каждой планете есть свой набор валют, которыми они торгуют. Поскольку валют слишком много, Хобер решил объявить набор из M валют (пронумерованных от 1 до M) в качестве официальных валют, которые можно использовать для торговли между планетами. Две планеты могут торговать тогда и только тогда, когда у них есть общая официальная валюта или если есть другая планета, с которой каждая из этих планет имеет общую официальную валюту. Например, предположим, что на планете A есть валюты - 1, 3, 4, на планете B - 5, 6, а на планете C - 6, 4. Планеты A и B все еще могут торговать через планету C (планета A -> C через валюту 4, а затем планета C -> B через валюту 6 и наоборот). Этот тип торговли может осуществляться с более чем одной планетой, выступающей в качестве посредника (т.е. планеты X и Y могут торговать через A, B, C, если XA использует общую валюту, AB имеет общую валюту, BC имеет общую валюту и наконец, у CY есть общая валюта). Хобер отмечает, что даже при соблюдении этих правил существуют планеты, на которых нет официальных валют, или группы планет, которые не имеют общей валюты с другими группами планет. Чтобы обеспечить торговлю между всеми планетами, он должен внедрить систему новой валюты для каждой из таких планет, у которых нет официальной или единой официальной валюты. Внедрение новой валютной системы обходится ему в 1 платиновую единицу на планету. Вы должны помочь Хоберу минимизировать затраты на торговлю между всеми планетами.
Вам будет дано N (2 <= N <= 50), что указывает количество планет, которые хотят участвовать в межгалактической торговле. Вам будет предоставлено M (2 <= M <= 50), что указывает количество официальных валют, пронумерованных от 1 до M. За этим последуют N строк, каждая из которых состоит из числа Ci, количества официальных валют, поддерживаемых планетой i. , за которыми следуют валюты C, которые торгуются на i-й планете. Вы должны вывести количество платиновых единиц, необходимое для торговли на всех планетах.
Примеры входных данных
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
5 5
0
3 4 1 5
2 3 4
0
1 2
Ожидаемые результаты
0
Планеты № 1 и № 2 могут торговать с использованием валюты 2. Планеты № 2 и № 3 могут торговать с использованием валюты 3. Планеты № 3 и № 4 могут торговать с использованием валюты 4. Планеты № 4 и № 5 могут торговать с использованием валюты 5. Это делает его можно торговать между любыми двумя планетами через ноль или более промежуточных планет. Таким образом, нет необходимости устанавливать новую валюту, и, следовательно, стоимость равна 0.
3
Планеты № 2 и № 3 могут торговать через валюту 4, но планеты № 1, № 4 и № 5 не имеют обмена валют друг с другом или с № 2 и № 3 и, следовательно, не могут торговать с кем-либо еще. Одна из валют с планет №2 или №3 может быть установлена на планетах №1, №4 и №5, что сделает возможной торговлю между всеми планетами. Поскольку валюта должна быть установлена на трех разных планетах, стоимость будет равна 3.
Примеры входов и выходов
Testcase Input Output Ссылка для загрузки Ссылка для запуска (также сохраняет код)
1
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0
Загрузить входной файл Выполнить с кодом
2
5 5
0
3 4 1 5
2 3 4
0
1 2
3
Загрузить входной файл Выполнить с кодом
Ограничение по времени на тестовый пример:
2 секунды
Если у вас есть компьютер с GCC / G ++ и вы хотите работать в автономном режиме, загрузите шаблон здесь и отправьте
Шаблоны кода:
Шаблон C: Trade.c
Шаблон C ++: Trade.cpp
Эта статья предоставлена Bharat. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию . Если вы готовы, проверьте свои навыки с помощью серий тестов TCS, Wipro, Amazon и Microsoft.