.
Но я что то не могу понять как это работает
Size: a a a
2021 July 02
EZ
Дпха ж?
EZ
Каждое уничтоженное ребро добавляет компоненту
EZ
Что именно в разборе не ясно
.
Мы просто удаляем вершину
.
и получается за раз мы удаляем несколько ребер
.
сразу
NK
какая тут дп, тут же просто формула
EZ
Ну вот, количество компонент это количество вершин минус количество ребер
.
Согласен
.
А как узнать сколько вершин у нас останется ?
EZ
Ну матожидание оставшихся вершин это просто сумма вероятностей (линейность матожидания)
.
Это походу как раз то что в разборе говорят M[V - E] = M[V] - M[E]
.
Я вот не могу понять M[V] почему мат ожидания количество вершин это просто сумма вероятностей того что вершина не удалится
.
Так как одна и та же вершина может встречаться в нескольких компонентах
EZ
EZ
Матожидание для одной вершины это p(v)*1+(1-p(v))*0=p(v)
.
а ну вот тут да теперь понял
.
А можете по подробнее как дпшкой решить ?
EZ
Да нет тут дпшки