Расчет множества компьютеров, зараженных вредоносными программами, в сети коммуникационных компьютеров?

Question

Немного предыстории: Это было очень давно, так как я закодированы в C (год скакать обратно в это действительно подавляющее

Мне нужен совет по реализации Может кто-нибудь может объяснить, как вы... будет идти о разработке этого я понять концепцию проблемы, но чувствовать себя потерянный о том, как даже начать реализацию

Вот ограничение:?.

Входные (с учетом алгоритма):

1. количество компьютеров в сети, обозначается как N. Предположим, что компьютеры названы 1, 2 .. до N.

2. Бревно, состоящий из списка троек (C1, C2, т). В каждой тройке C1 и C2 являются именами компьютеров, а t является меткой времени. Если в логе появляется (C1, C2, t), то это означает, что C1 и C2 обмениваются друг с другом в момент времени t. (t всегда будет целым числом = = 0)

3. Существует компьютер, CBad, который является именем компьютера, на котором впервые было обнаружено вредоносное ПО. Существует также временная метка tBad, в которой вредоносное ПО было введено в CBad.

Механика инфекции:

1. Если на компьютере, говорят С0, заражен и другой компьютер, С1 связывается с С0 в момент времени Т, то С будет также заражаются. (и он заразится в момент времени t.)

2. Если компьютер заражен в момент времени t, он заражен в любое время t1> = t (другими словами, он считается зараженным в этой точке и любым указать впоследствии)

Ожидаемый результат здесь является TXT-файл отображает список зараженных компьютеров в результате CBad (наш пациент 0) число инфицированных в момент времени ТБАД.

Мы обсуждали минимальные алгоритмы остовного дерева (в частности Prims и Kruskals). Я уверен, что он хочет использовать один из них при решении этой проблемы.

Мысли до сих пор: Моя теория до сих пор заключается в том, что в каждом списке триплетов C1 и C2 представляют две вершины, составляющие ребро. И временная метка t представляет стоимость/вес/что-то из этого края. Как-то мне нужно построить связанный, неориентированный граф, а затем запустить (алгоритм Крускаля?), Чтобы найти множество? ... Я просто не знаю. Здесь я чувствую себя идиотом. :(

Answer 1

Вы слишком задумываетесь о вещах. Хотя представление о части сценария можно рассматривать как ориентированный граф, это представление, по-видимому, не поддается какой-либо полезной оптимизации (особенно потому, что t ничего не представляет с весовым поведением.) Вместо этого, рассмотрим простой подход:

• Инициализировать множество S узлов (представляющий «зараженные» компьютеры), чтобы содержать только CBad.
• Удалить все троек из вашего списка, у которых есть t < tBad.
• Сортировка оставшихся троек по t.
• Для вашего нового отсортированного списка каждого тройного (C1, C2, t):
  • Если C1 в S, добавьте C2 к S.
• Возврат содержимого S.

Это O(n log n), поскольку нам пришлось отсортировать список. Может быть какой-то умный способ сделать это O(n), но я вроде как сомневаюсь в этом.